fork download
copy 
  1. /// USACO 2016 December Contest, Gold - Moocast
  2. /// https://u...content-available-to-author-only...o.org/index.php?page=viewproblem2&cpid=669
  3. /// Author: Qwerty
  4. #include<bits/stdc++.h>
  5. #define fi first
  6. #define se second
  7. #define ll long long
  8. using namespace std;
  9. const int MAXN = 1010;
  10. pair<int, int> c[MAXN];
  11. vector<pair<int, pair<int, int>>> edge;
  12. int n;
  13. struct DSU{
  14.     int parent[MAXN];
  15.     DSU(){
  16.         for (int i = 1; i <= n; i++){
  17.              parent[i] = i;
  18.         }
  19.     }
  20.     int find(int u){
  21.         if (parent[u] != u) return parent[u] = find(parent[u]);
  22.         return parent[u];
  23.     }
  24.     bool unite(int u, int v){
  25.         u = find(u);
  26.         v = find(v);
  27.         if (u == v) return false;
  28.         parent[u] = v;
  29.         return true;
  30.     }
  31. };
  32. int dist(pair<int, int> &a, pair<int, int> &b){
  33.     return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
  34. }
  35. int main(){
  36.     //freopen("moocast.in", "r", stdin);
  37.     //freopen("moocast.out", "w", stdout);
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cin >> n;
  41.     for (int i = 1; i <= n; i++){
  42.          cin >> c[i].first >> c[i].second;
  43.     }
  44.     for (int i = 1; i <= n; i++){
  45.          for (int j = i + 1; j <= n; j++){
  46.               edge.push_back({dist(c[i], c[j]), {i, j}});
  47.          }
  48.     }
  49.     sort(edge.begin(), edge.end());
  50.     DSU s;
  51.     int cnt = 0;
  52.     int ans = 0;
  53.     for (auto e: edge){
  54.         int w = e.fi;
  55.         int u = e.se.fi;
  56.         int v = e.se.se;
  57.         if (s.unite(u, v)){
  58.             ans = max(ans, w);
  59.             cnt++;
  60.         }
  61.         if (cnt == n - 1){
  62.             break;
  63.         }
  64.     }
  65.     cout << ans << '\n';
  66. }
  67.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
1 3
5 4
7 2
6 1
stdout
copy 
17
https://ideone.com/o1v3pq
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!