fork download
copy 
  1. /// USACO 2021 December Contest, Silver - Connecting Two Barns
  2. /// https://u...content-available-to-author-only...o.org/index.php?page=viewproblem2&cpid=1159
  3. /// Author: Qwerty
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. const int MAXN = 1e5 + 100;
  7. int n, m;
  8. vector<int> a[MAXN];
  9. int vis[MAXN];
  10. vector<int> comp[MAXN];
  11. int cnt = 1;
  12. int g1, gn;
  13. void dfs(int u){
  14.     if (u == 1) g1 = cnt;
  15.     if (u == n) gn = cnt;
  16.     vis[u] = 1;
  17.     comp[cnt].push_back(u);
  18.     for (int v: a[u]){
  19.          if (vis[v] == 0){
  20.              dfs(v);
  21.          }
  22.     }
  23. }
  24. long long cal(int u, int v){
  25.     long long dist = 1e18;
  26.     for (int x: comp[v]){
  27.          int index = lower_bound(comp[u].begin(), comp[u].end(), x) - comp[u].begin();
  28.          if (index != 0) dist = min(dist, 1LL * abs(comp[u][index - 1] - x));
  29.          if (index != comp[u].size()) dist = min(dist, 1LL * abs(comp[u][index] - x));
  30.     }
  31.     return dist * dist;
  32. }
  33. int main(){
  34.     ios_base::sync_with_stdio(0);
  35.     cin.tie(0);
  36.     int t;
  37.     cin >> t;
  38.     while (t--){
  39.         cnt = 1;
  40.         cin >> n >> m;
  41.         for (int i = 1; i <= m; i++){
  42.              int x, y;
  43.              cin >> x >> y;
  44.              a[x].push_back(y);
  45.              a[y].push_back(x);
  46.         }
  47.         long long ans = 1e18;
  48.         for (int i = 1; i <= n; i++){
  49.              if (vis[i] == 0){
  50.                  dfs(i);
  51.                  cnt++;
  52.              }
  53.         }
  54.         cnt--;
  55.         sort(comp[g1].begin(), comp[g1].end());
  56.         sort(comp[gn].begin(), comp[gn].end());
  57.         for (int i = 1; i <= cnt; i++){
  58.              ans = min(ans, cal(g1, i) + cal(gn, i));
  59.         }
  60.         cout << ans << '\n';
  61.         for (int i = 1; i <= n; i++) {
  62.              a[i].clear();
  63.              vis[i] = 0;
  64.              comp[i].clear();
  65.         }
  66.     }
  67. }
  68.  
Success #stdin #stdout 0.01s 8724KB
comments (?)
stdin
copy 
2
5 2
1 2
4 5
5 3
1 2
2 3
4 5
stdout
copy 
2
1
https://ideone.com/AI4hB5
language:
C++14 (gcc 8.3)
created:
4 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!