fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define nl '\n'
  5. #define yes cout << "Yes" << nl
  6. #define no cout << "No" << nl
  7. #define Yes cout << "YES" << nl
  8. #define No cout << "NO" << nl
  9. #define all(a) a.begin(),a.end()
  10. #define rall(a) a.rbegin(),a.rend()
  11. #define pb push_back
  12. #define MD 1000000007
  13. #define fastio                        \
  14.    ios_base::sync_with_stdio(false); \
  15.    cin.tie(NULL);                    \
  16.    cout.tie(NULL);
  17.  
  18. const int N = 1e5+2;
  19.  
  20. struct DSU {
  21.    vector<int> par, rnk; int c;
  22.    DSU(int n) : par(n+1), rnk(n+1)
  23.    {
  24.       for(int i=1;i<=n;++i) par[i]=i;
  25.    }
  26.    int find(int i) {
  27.       return (par[i]==i?i:find(par[i]));
  28.    }
  29.    bool same(int i, int j){
  30.       return find(i) == find(j);
  31.    }
  32.    int Union(int i, int j){
  33.       if((i=find(i)) == (j =find(j))) return -1;
  34.       else c--;
  35.       if(rnk[i]>rnk[j]) swap(i,j);
  36.  
  37.       par[i]=j;
  38.       if(rnk[i]==rnk[j]) rnk[j]++;
  39.       return j;
  40.    }
  41. };
  42.  
  43.  
  44. vector<pair<int, int>> adj[N];
  45.  
  46. void solution() {
  47.    ll n, m, x, y;
  48.    cin >> n >> m;
  49.  
  50.    for(int i=0;i<n;++i) adj[i].clear();
  51.  
  52.    while(m--){
  53.       int u, v, w; cin >> u >> v >> w;
  54.       // edges.push_back({u,v,w});
  55.  
  56.       adj[u].push_back({v,w});
  57.    }
  58.    priority_queue<pair<int,int>> pq;
  59.    DSU ds(n);
  60.    for(auto [i, w]: adj[0]) pq.push({-w,i});
  61.    ll ans = 0;
  62.    while(pq.size()) {
  63.       int v = pq.top().second;
  64.       int w = -pq.top().first;
  65.  
  66.       pq.pop();
  67.  
  68.       if(ds.Union(0,v) !=-1 ) {
  69.          for(auto [i, xx]: adj[v]) pq.push({-xx,i});
  70.          ans+=w;
  71.       }
  72.    }
  73.    set<int> par;
  74.    for(int i=0;i<n;++i) par.insert(ds.find(i));
  75.  
  76.    if(par.size()!=1) cout << "Possums!" << nl;
  77.    else cout << ans << nl;
  78. }
  79.  
  80. int main() {
  81.    fastio;
  82.    ll t = 1;
  83.    cin >> t;
  84.    for (ll i = 1; i <= t; i++) {
  85.        cout << "Case #" << i << ": ";
  86.        solution();
  87.    }
  88.    return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 5952KB
comments (?)
stdin
copy 
15
4 14
3 1 4
3 1 3
3 2 3
3 2 6
1 3 9
3 1 5
2 0 9
0 1 8
0 2 8
3 1 2
2 1 3
1 3 7
1 3 5
1 0 1
4 17
3 0 6
3 0 3
1 2 8
2 3 4
0 1 4
0 1 3
3 2 7
3 1 4
1 2 2
1 0 8
0 2 3
3 1 3
3 2 6
3 2 2
3 1 0
3 0 7
3 1 0
4 18
0 2 0
3 2 3
3 2 4
3 2 8
3 2 2
0 1 8
1 2 2
0 1 3
1 3 8
3 0 2
0 2 6
0 2 0
1 3 0
2 3 9
1 0 5
0 3 8
1 2 0
0 2 4
5 19
4 3 1
1 0 4
3 4 7
4 2 6
4 0 6
3 0 2
0 2 4
2 3 9
0 1 7
4 2 2
1 0 7
2 3 2
4 2 5
2 3 7
1 2 2
3 4 6
3 4 6
1 0 6
1 2 9
5 22
1 4 6
4 1 5
3 0 9
0 4 8
1 3 1
1 3 7
1 4 9
4 0 2
3 0 9
4 0 2
1 0 8
3 2 9
1 0 1
3 2 6
0 3 9
2 4 4
1 4 3
0 1 0
1 3 2
3 2 3
3 1 0
4 2 9
5 24
3 0 3
2 1 2
1 0 7
0 3 6
3 0 9
2 4 0
0 1 9
3 0 4
1 4 2
3 2 3
2 0 3
1 4 9
2 0 9
3 4 1
1 0 0
1 0 7
4 0 1
3 0 2
0 1 0
0 1 1
4 1 4
3 4 0
1 0 4
0 2 5
5 27
2 0 6
2 0 3
1 4 6
3 4 0
3 0 2
0 1 8
0 4 1
1 0 0
3 0 9
3 2 0
2 0 2
3 2 4
3 0 5
2 4 4
4 1 8
0 3 9
4 0 8
2 3 4
4 3 7
0 1 8
4 0 4
1 2 0
0 3 0
2 1 3
0 4 2
3 1 5
4 0 0
5 30
1 3 5
1 2 4
4 0 6
4 3 3
2 3 2
1 2 1
0 2 6
3 0 9
3 1 4
4 3 9
0 3 4
1 3 3
3 1 5
1 4 5
0 2 7
4 3 8
2 0 5
2 4 3
3 4 7
1 0 6
4 2 1
0 2 4
2 3 8
1 0 1
0 1 6
4 2 0
4 2 3
3 1 6
4 3 7
4 1 6
5 32
1 2 2
3 0 3
3 4 4
0 4 6
4 0 8
1 3 1
3 0 5
4 0 3
2 4 9
0 4 4
0 4 1
3 0 9
0 3 4
4 0 5
2 3 4
1 2 2
1 3 2
0 4 2
4 3 9
2 4 0
3 4 7
0 3 2
0 2 6
2 4 9
1 4 7
4 3 7
1 4 5
3 2 3
2 3 1
0 1 4
3 4 8
4 0 3
5 32
1 4 7
0 1 8
4 0 8
1 2 7
2 3 6
3 4 0
1 2 8
1 4 6
3 0 8
3 4 7
4 1 9
4 2 1
1 2 1
1 0 4
3 2 2
4 1 9
2 0 5
0 2 8
3 1 0
0 2 2
4 1 9
4 0 5
2 0 0
2 3 7
2 1 4
0 2 1
0 2 8
1 2 6
0 3 8
3 1 3
3 0 4
2 4 5
5 36
3 2 0
0 1 9
3 0 3
4 3 8
0 1 0
0 2 4
4 0 9
3 4 9
4 2 2
2 1 5
1 2 1
1 2 9
4 0 2
2 0 0
2 4 3
2 0 2
0 2 0
3 0 3
3 4 1
1 0 2
3 2 6
3 1 4
4 2 4
1 2 2
3 1 8
3 0 1
2 3 4
4 0 1
3 2 0
4 2 2
2 0 7
0 2 5
1 2 2
2 1 6
2 4 8
2 3 7
5 40
2 4 5
1 3 4
0 3 8
4 2 5
3 4 6
4 3 4
0 2 8
0 2 0
1 0 5
4 1 6
3 2 6
1 2 4
0 1 2
4 1 9
3 4 8
4 1 4
4 0 1
4 3 5
1 0 0
4 3 6
4 2 8
0 2 4
4 2 9
1 0 3
4 2 1
3 0 8
2 4 1
4 2 6
0 4 9
4 2 3
3 2 4
4 0 2
1 4 7
1 4 4
0 4 5
3 4 5
3 4 1
4 3 2
3 4 9
0 3 7
5 40
4 3 5
3 2 2
0 1 0
1 3 3
4 0 0
2 1 4
2 3 4
4 2 3
3 4 3
0 3 4
2 3 8
0 2 7
1 3 2
2 4 8
0 1 1
0 3 3
2 4 5
3 4 3
3 2 5
4 2 8
1 3 2
1 2 5
0 4 4
3 1 1
4 2 7
2 4 3
3 0 0
2 1 6
3 1 7
1 4 1
0 1 9
3 1 4
0 1 3
0 2 6
2 4 6
2 4 2
1 4 6
2 3 8
2 0 7
0 2 2
5 44
3 0 7
0 2 8
4 0 5
1 3 9
4 3 1
1 2 6
4 0 9
0 3 1
2 4 3
0 2 1
4 2 6
2 1 0
3 4 1
1 2 7
2 0 2
2 1 9
4 0 8
0 2 6
2 3 1
3 2 9
2 3 0
2 1 1
2 3 0
2 4 7
3 2 5
1 4 8
4 3 7
4 0 0
2 1 7
3 2 4
3 2 3
2 3 3
2 3 9
0 2 0
1 0 0
3 1 0
0 3 8
1 3 7
1 3 3
2 3 4
0 4 3
2 1 9
4 1 3
2 0 0
5 44
4 0 2
0 4 4
0 3 5
2 3 6
1 2 6
2 3 5
4 1 2
0 2 8
1 2 7
4 2 5
1 3 6
0 2 2
1 3 3
0 4 2
4 2 2
1 2 0
1 4 7
4 0 5
4 2 4
3 1 5
2 1 5
4 2 7
0 1 6
2 3 2
2 0 8
4 3 0
3 0 0
1 0 1
3 0 7
0 1 2
2 3 9
1 2 4
0 4 3
0 3 6
3 1 6
3 0 7
1 4 8
0 1 2
4 0 2
1 0 2
3 4 9
0 2 5
2 3 8
0 4 9
stdout
copy 
Case #1: 16
Case #2: 10
Case #3: 3
Case #4: 19
Case #5: 7
Case #6: 13
Case #7: 3
Case #8: 15
Case #9: 10
Case #10: 16
Case #11: 7
Case #12: 5
Case #13: 5
Case #14: 1
Case #15: 6
https://ideone.com/iaUyL4
language:
C++14 (gcc 8.3)
created:
13 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!