fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <functional>
  5. #include <climits>
  6.  
  7. #define int long long
  8. using namespace std;
  9.  
  10. #define all(c) c.begin(), c.end()
  11. #define line "\n"
  12.  
  13. typedef vector<int> vi;
  14. typedef vector<vector<int>> vvi;
  15.  
  16. vvi graph, dsu;
  17. vector<bool> vis;
  18. vi travel;
  19.  
  20. void dfs(int node) {
  21.     if (vis[node]) return;
  22.     vis[node] = true;
  23.     travel.push_back(node);
  24.     for (int adj : graph[node]) dfs(adj);
  25. }
  26.  
  27. void solve() {
  28.     int n, m; cin >> n >> m;
  29.  
  30.     graph.assign(n + 1, vector<int>());
  31.     vis.assign(n + 1, false);
  32.     dsu.clear();
  33.  
  34.     for (int i = 0; i < m; i++) {
  35.         int x, y; cin >> x >> y;
  36.         graph[x].push_back(y);
  37.         graph[y].push_back(x);
  38.     }
  39.  
  40.     travel.clear();
  41.     dfs(1);
  42.     sort(all(travel));
  43.     vi dsu1 = travel;
  44.  
  45.     travel.clear();
  46.     dfs(n);
  47.     sort(all(travel));
  48.     vi dsun = travel;
  49.  
  50.     for (int i = 2; i < n; i++) {
  51.         if (!vis[i]) {
  52.             travel.clear();
  53.             dfs(i);
  54.             dsu.push_back(travel);
  55.         }
  56.     }
  57.  
  58.     int ans = LLONG_MAX;
  59.     for (int x : dsu1) {
  60.         auto it = upper_bound(all(dsun), x);
  61.         if (it != dsun.end()) ans = min(ans, (*it) * (*it));
  62.         if (it != dsun.begin()) {
  63.             --it;
  64.             ans = min(ans, (*it) * (*it));
  65.         }
  66.     }
  67.  
  68.     for (auto &v : dsu) {
  69.         for (int x : v) {
  70.             int val1 = LLONG_MAX, val2 = LLONG_MAX;
  71.             auto it = upper_bound(all(dsun), x);
  72.             if (it != dsun.end()) val1 = min(val1, (*it - x) * (*it - x));
  73.             if (it != dsun.begin()) {
  74.                 --it;
  75.                 val1 = min(val1, (*it - x) * (*it - x));
  76.             }
  77.             it = upper_bound(all(dsu1), x);
  78.             if (it != dsu1.end()) val2 = min(val2, (*it - x) * (*it - x));
  79.             if (it != dsu1.begin()) {
  80.                 --it;
  81.                 val2 = min(val2, (*it - x) * (*it - x));
  82.             }
  83.             ans = min(ans, val1 + val2);
  84.         }
  85.     }
  86.  
  87.     if (dsu1 == dsun) cout << 0 << line;
  88.     else cout << ans << line;
  89. }
  90.  
  91. int32_t main() {
  92.     ios_base::sync_with_stdio(false);
  93.     cin.tie(NULL);
  94.     cout.tie(NULL);
  95.  
  96.     int t; cin >> t;
  97.     while (t--) {
  98.         solve();
  99.     }
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
2
5 2
1 2
4 5
5 3
1 2
2 3
4 5
stdout
copy 
2
16
https://ideone.com/7wHwbb
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!