fork download
copy 
  1. /*
  2. Task: 1245D
  3. Date: Dec 18, 2019
  4. Author: aLittleLove (Minh Vu)
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #define fi first
  9. #define se second 
  10.  
  11. using namespace std;
  12. const int N = 2e3 + 5;;
  13. typedef pair<int, int> pi;
  14.  
  15. struct Edge
  16. {
  17.     int u, v; int64_t w;
  18.     bool operator < (const Edge &oth) const 
  19.     {
  20.         return w<oth.w;
  21.     }
  22. };
  23.  
  24. Edge e[N*(N + 1)];
  25. int n, m, c[N], k[N], pa[N<<1];
  26. pi a[N];
  27. int64_t ans;
  28.  
  29. int root(int x)
  30. {
  31.     return x==pa[x] ? x : pa[x] = root(pa[x]);
  32. }
  33.  
  34. bool join(int x, int y)
  35. {
  36.     if ((x=root(x))==(y=root(y))) return false;
  37.     pa[y] = x;
  38.     return true;
  39. }
  40.  
  41. int main()
  42. {
  43.     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  44.     cin >> n;
  45.     for (int i=1; i<=n; i++) cin >> a[i].fi >> a[i].se;
  46.     for (int i=1; i<=n; i++) cin >> c[i];
  47.     for (int i=1; i<=n; i++) cin >> k[i];
  48.     for (int i=1; i<=n; i++)
  49.     {
  50.         for (int j=1; j<=n; j++)
  51.         {
  52.             if (i==j) continue;
  53.             e[++m].u = i; e[m].v = j;
  54.             e[m].w = 1ll * (abs(a[i].fi - a[j].fi) + abs(a[i].se - a[j].se)) * (k[i] + k[j]);
  55.         }
  56.     }
  57.     for (int i=1; i<=n; i++) 
  58.     {
  59.         e[++m].u = i; e[m].v = n + 1;
  60.         e[m].w = c[i];
  61.     }
  62.     for (int i=1; i<=n+1; i++) pa[i] = i;
  63.     sort(e+1,e+m+1);
  64.     vector<int> build; vector<pi> connect;
  65.     for (int i=1; i<=m; i++)
  66.     {
  67.         int x = root(e[i].u), y = root(e[i].v);
  68.         if (x!=y)
  69.         {
  70.             ans += e[i].w;
  71.             if (e[i].v==n+1) build.push_back(e[i].u);
  72.             else connect.push_back({e[i].u, e[i].v});
  73.             join(x, y);
  74.         }
  75.     }
  76.     cout << ans << '\n';
  77.     cout << build.size() << '\n';
  78.     for (int x: build) cout << x << " ";
  79.     cout << '\n';
  80.     cout << connect.size() << '\n';
  81.     for (pi x: connect) cout << x.fi << " " << x.se << '\n';
  82. }
Success #stdin #stdout 0s 4956KB
comments (?)
stdin
copy 
3
2 1
1 2
3 3
23 2 23
3 2 3
stdout
copy 
27
1
2 
2
1 2
2 3
https://ideone.com/lNDgEc
Codeforces 1245D
language:
C++14 (gcc 8.3)
created:
4 years 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!