fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define  ll long long
  4. #define int long long
  5. const int N = 4e5+5;
  6. int n;vector<pair<int,int>> adj[N];
  7.  
  8. struct edge{
  9.     int a,b,cost;
  10.     edge(int x,int y,int z):a(x),b(y),cost(z){}
  11.     bool operator<(edge &x)const{
  12.         return cost<x.cost;
  13.     }
  14. };
  15. int parent[N],group[N];
  16. struct dsu
  17. {
  18.     dsu()
  19.     {
  20.         for(int i=0;i<N;i++)
  21.         {
  22.             parent[i]=i;
  23.             group[i]=1;
  24.         }
  25.     }
  26.     int find(int i)
  27.     {
  28.         if(parent[i]==i)
  29.         {
  30.             return i;
  31.         }
  32.         return parent[i]= find(parent[i]);
  33.     }
  34.     bool samegroup(int x,int y)
  35.     {
  36.         return find(x)==find(y);
  37.     }
  38.     void merge(int x,int y)
  39.     {
  40.         int leader1=find(x);
  41.         int leader2=find(y);
  42.         if(leader1==leader2) return;
  43.         if(group[leader1]>group[leader2]) swap(leader1,leader2);
  44.         group[leader2]+=group[leader1];
  45.         parent[leader1]=leader2;
  46.     }
  47.     int getsize(int x)
  48.     {
  49.         return group[find(x)];
  50.     }
  51. };
  52. bool vis[N]={};
  53.  
  54. /////////////////////////////////////////////
  55. const int Log=23;
  56. int mx[N][Log],anc[N][Log],level[N],s[N];vector<pair<int,int>>adj2[N];
  57. void BuildAncestors(int node,int parent,int cost)
  58. {
  59.     level[node]=level[parent]+1;
  60.     anc[node][0]=parent;
  61.     mx[node][0]=cost;
  62.     for(int o=1;o<Log;o++)
  63.     {
  64.         int p=anc[node][o-1];
  65.         anc[node][o]=anc[p][o-1];
  66.         mx[node][o]=max(mx[p][o-1],mx[node][o-1]);
  67.     }
  68.     for(auto it:adj2[node])
  69.     {
  70.         if(it.first==parent)
  71.         {
  72.             continue;
  73.         }
  74.         BuildAncestors(it.first,node,it.second);
  75.     }
  76. }
  77. int KthAncestor(int node,int k)
  78. {
  79.     for(int o=Log-1;o>=0;o--)
  80.     {
  81.         if(k&(1<<o))
  82.         {
  83.             node=anc[node][o];
  84.         }
  85.     }
  86.     return node;
  87. }
  88. int MX(int node,int k)
  89. {
  90.     int ret=0;
  91.     for(int o=Log-1;o>=0;o--)
  92.     {
  93.         if(k&(1<<o))
  94.         {
  95.             ret=max(ret,mx[node][o]);
  96.             node=anc[node][o];
  97.         }
  98.     }
  99.     return ret;
  100. }
  101. int LCA(int u,int v)
  102. {
  103.     if(level[u]<level[v])
  104.     {
  105.         swap(u,v);
  106.     }
  107.     u=KthAncestor(u,level[u]-level[v]);
  108.     if(u==v)
  109.     {
  110.         return u;
  111.     }
  112.     for(int i=Log-1;i>=0;i--)
  113.     {
  114.         if(anc[u][i]!=anc[v][i])
  115.         {
  116.             u=anc[u][i];
  117.             v=anc[v][i];
  118.         }
  119.     }
  120.     return anc[u][0];
  121. }
  122. signed main()
  123. {
  124.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  125.     cin>>n;
  126.     map<string,int>m;
  127.     int idx=1;
  128.     vector<edge>ed;
  129.     for(int i=0;i<n;i++)
  130.     {
  131.         string x,y;int c;cin>>x>>y>>c;
  132.         int a,b;
  133.         if(m.find(x)!=m.end())a=m[x];
  134.         else a=m[x]=idx++;
  135.         if(m.find(y)!=m.end())b=m[y];
  136.         else b=m[y]=idx++;
  137.         ed.push_back(edge(a,b,c));
  138.         adj[a].push_back({b,c});
  139.         adj[b].push_back({a,c});
  140.     }
  141.  
  142.     sort(ed.begin(),ed.end());
  143.     dsu d;
  144.     map<pair<int,int>,bool>mp;
  145.     vector<edge>ed2,ed3;
  146.     for(int i=0;i<n;i++){
  147.         if(d.samegroup(ed[i].a,ed[i].b)){
  148.             ed3.push_back(ed[i]);
  149.             continue;
  150.         }
  151.         d.merge(ed[i].a,ed[i].b);
  152.         adj2[ed[i].a].push_back({ed[i].b,ed[i].cost});
  153.         adj2[ed[i].b].push_back({ed[i].a,ed[i].cost});
  154.         ed2.push_back(ed[i]);
  155.     }
  156.     if(d.getsize(1)!=m.size()){
  157.         cout<<-1;
  158.         return 0;
  159.     }
  160.     BuildAncestors(1,1,0);
  161.     ll ans=0;
  162.     for(auto it:ed2)
  163.     {
  164.         ans+=it.cost;
  165.     }
  166.     for(auto it:ed3)
  167.     {
  168.         int lc=LCA(it.a,it.b);
  169.         if(max(MX(it.a,level[it.a]-level[lc]),MX(it.b,level[it.b]-level[lc]))>=it.cost) ans+=it.cost;
  170.     }
  171.     cout<<ans;
  172. }
  173.  
Success #stdin #stdout 0.02s 35540KB
comments (?)
stdin 
5
a b 1
b c 2
a c 2
b d 4
a d 5
stdout 
9
https://ideone.com/S5XTcq
language:
C++14 (gcc 8.3)
created:
11 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!