Submission #417384

#TimeUsernameProblemLanguageResultExecution timeMemory
417384kshitij_sodaniToll (APIO13_toll)C++14
0 / 100
16 ms23884 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second #define endl '\n' int t; int par[1000001]; int par2[1000001]; vector<pair<int,int>> adj[1000001]; int it[1000001]; int find(int no){ if(par[no]==no){ return par[no]; } par[no]=find(par[no]); return par[no]; } int co=0; int st[1000001]; int endd[1000001]; bool vis[600001]; llo ss[100001]; llo val[100001]; //int par2[100001]; void dfs(int no,int par=-1){ st[no]=co; co++; par2[no]=par; ss[no]=it[no]; for(auto j:adj[no]){ if(vis[j.b]==0){ continue; } if(j.a!=par){ dfs(j.a,no); ss[no]+=ss[j.a]; } } endd[no]=co-1; } bool ispar(int x,int y){ return st[x]<=st[y] and endd[x]>=endd[y]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m,k; cin>>n>>m>>k; vector<pair<int,pair<int,int>>> ed; for(int i=0;i<m;i++){ int aa,bb,cc; cin>>aa>>bb>>cc; aa--; bb--; ed.pb({cc,{aa,bb}}); } sort(ed.begin(),ed.end()); for(int i=0;i<ed.size();i++){ int aa=ed[i].b.a; int bb=ed[i].b.b; adj[aa].pb({bb,i}); adj[bb].pb({aa,i}); } vector<pair<int,int>> zz; for(int i=0;i<k;i++){ int aa,bb; cin>>aa>>bb; aa--; bb--; zz.pb({aa,bb}); adj[aa].pb({bb,m+i}); adj[bb].pb({aa,m+i}); } for(int i=0;i<n;i++){ cin>>it[i]; } llo ans=0; vector<pair<int,pair<int,int>>> dd; for(int i=1;i<(1<<k);i++){ for(int j=0;j<n;j++){ par[j]=j; adj[i].clear(); } for(int j=0;j<m+k;j++){ vis[j]=0; } int st=1; for(int j=0;j<k;j++){ if((1<<j)&i){ int x=find(zz[j].a); int y=find(zz[j].b); if(x==y){ st=0; break; } vis[j+m]=1; par[x]=y; // adj[zz[j].a].pb(zz[j].b); // adj[zz[j].b].pb(zz[j].a); } } if(st==0){ continue; } dd.clear(); int ind2=-1; for(auto j:ed){ ind2++; int x=find(j.b.a); int y=find(j.b.b); if(x!=y){ vis[ind2]=1; par[x]=y; continue; //adj[j.b.a].pb(j.b.b); //adj[j.b.b].pb(j.b.a); } else{ dd.pb(j); } } //continue; co=0; dfs(0); for(int j=0;j<n;j++){ par[j]=par2[j]; val[j]=1e9; } //continue; for(auto j:dd){ int x=j.b.a;//find(j.b.a); int y=j.b.b;//find(j.b.b); int cur=x; vector<int> xx; //continue; if(!ispar(x,y)){ while(!ispar(cur,y)){ xx.pb(cur); //cout<<cur<<","; cur=par[cur]; } //cout<<endl; } for(int ii=0;ii<xx.size();ii++){ val[xx[ii]]=min(val[xx[ii]],(llo)j.a); par[xx[ii]]=cur; } cur=y; xx.clear(); if(!ispar(y,x)){ while(!ispar(cur,x)){ xx.pb(cur); cur=par[cur]; } } for(int ii=0;ii<xx.size();ii++){ val[xx[ii]]=min(val[xx[ii]],(llo)j.a); par[xx[ii]]=cur; } } llo su=0; for(int j=0;j<k;j++){ if((1<<j)&i){ if(ispar(zz[j].a,zz[j].b)){ su+=ss[zz[j].b]*val[zz[j].b]; } else{ su+=ss[zz[j].a]*val[zz[j].a]; } } } ans=max(ans,su); } cout<<ans<<endl; return 0; }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:66:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i=0;i<ed.size();i++){
      |              ~^~~~~~~~~~
toll.cpp:156:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |    for(int ii=0;ii<xx.size();ii++){
      |                 ~~^~~~~~~~~~
toll.cpp:168:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |    for(int ii=0;ii<xx.size();ii++){
      |                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...