Submission #1109326

#TimeUsernameProblemLanguageResultExecution timeMemory
1109326vivkostovToll (APIO13_toll)C++14
0 / 100
4 ms21072 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const long long int inf=2000000000000000001; struct cell { long long int to,st; }; struct poin { long long int a,b,c; }; bool cmp(poin a1,poin a2) { return a1.c<a2.c; } long long int n,m,k,br[100005],l[100],r[100],used[100005],lead[100005],sz[100005],num[100005],use[100005],basic_lead[100005],numb,group[200005]; long long int otg[2000005],par[200005],parto[100005],dpmi[200005],dpbr[200005],used1[100]; cell mi[100005]; poin f[300005]; vector<cell>v[100005]; vector<cell>vert[100005]; stack<pair<int,int>>s; void prec() { for(int i=1;i<=n;i++) { lead[i]=i; sz[i]=1; num[i]=br[i]; } for(int i=1;i<=n;i++) { mi[i].st=inf; } } int get_lead(int beg) { if(beg==lead[beg])return beg; return lead[beg]=get_lead(lead[beg]); } int get_lead2(int beg) { if(beg==lead[beg])return beg; return get_lead2(lead[beg]); } void add1(int a,int b) { a=get_lead(a); b=get_lead(b); if(a==b||(used[a]&&used[b]))return; if(sz[a]<sz[b])swap(a,b); if(used[b])used[a]=1; lead[b]=a; sz[a]+=sz[b]; num[a]+=num[b]; } void add2(int a,int b) { a=get_lead2(a); b=get_lead2(b); if(sz[a]<sz[b])swap(a,b); lead[b]=a; sz[a]+=sz[b]; num[a]+=num[b]; pair<int,int>p; p.first=a; p.second=b; s.push(p); } void rem(int brx) { int a,b; for(int i=1;i<=brx;i++) { a=s.top().first,b=s.top().second; sz[a]-=sz[b]; num[a]-=num[b]; lead[b]=b; s.pop(); } } void get_basic() { memset(used,0,sizeof(used)); int l; for(int i=1;i<=n;i++) { l=get_lead(i); if(!used[l]) { used[l]=1; numb++; basic_lead[numb]=l; } } } void Clear() { int w; for(int i=1;i<=numb;i++) { w=basic_lead[i]; v[w].clear(); dpbr[w]=0; dpmi[w]=inf; } memset(used1,0,sizeof(used1)); } void get_group() { for(int i=1;i<=n;i++) { group[i]=get_lead(i); } } void fill_vert() { int w1,w2,brx=0; cell h; for(int i=1;i<=m;i++) { w1=group[f[i].a]; w2=group[f[i].b]; if(w1!=w2) { h.to=w2; h.st=f[i].c; vert[w1].push_back(h); h.to=w1; vert[w2].push_back(h); add2(w1,w2); brx++; } } rem(brx); /*cout<<numb<<endl; for(int i=1;i<=numb;i++) { cout<<basic_lead[i]<<endl; for(int j=0;j<vert[basic_lead[i]].size();j++) { cout<<vert[basic_lead[i]][j].to<<" "<<vert[basic_lead[i]][j].st<<endl; } cout<<endl; } cout<<endl; */ } int dfs1(int beg,int p) { int sum=0,w; dpbr[beg]=num[beg]; for(int i=0;i<vert[beg].size();i++) { if(!used1[vert[beg][i].to]) { dpmi[beg]=min(dpmi[beg],vert[beg][i].st); } } for(int i=0;i<v[beg].size();i++) { w=v[beg][i].to; if(w!=p) { sum+=dfs1(w,beg); dpbr[beg]+=dpbr[w]; dpmi[beg]=min(dpmi[beg],dpmi[w]); if(v[beg][i].st==-1) { sum+=dpbr[w]*dpmi[w]; } } if(beg==1)memset(used1,0,sizeof(used1)); } //cout<<dpbr[beg]<<" "<<dpmi[beg]<<" "<<beg<<" "<<sum<<endl; used1[beg]=1; return sum; } void calc(int ind) { int w1,w2,brx=0; cell h; for(int i=1;i<=k;i++) { if(use[i]) { w1=get_lead2(l[i]); w2=get_lead2(r[i]); if(w1!=w2) { h.to=group[r[i]]; h.st=-1; v[group[l[i]]].push_back(h); h.to=group[l[i]]; v[group[r[i]]].push_back(h); add2(w1,w2); brx++; } } } int bl1,bl2; //cout<<numb<<endl; for(int i=1;i<=numb;i++) { bl1=basic_lead[i]; for(int j=0;j<vert[bl1].size();j++) { w1=get_lead2(bl1); w2=get_lead2(vert[bl1][j].to); bl2=vert[bl1][j].to; if(w1!=w2) { h.to=bl2; h.st=vert[bl1][j].st; v[bl1].push_back(h); h.to=bl1; v[bl2].push_back(h); add2(w1,w2); brx++; } } } rem(brx); otg[ind]=dfs1(group[1],0); /*cout<<endl; cout<<ind<<endl; for(int i=1;i<=numb;i++) { cout<<basic_lead[i]<<endl; for(int j=0;j<v[basic_lead[i]].size();j++) { cout<<v[basic_lead[i]][j].to<<" "<<v[basic_lead[i]][j].st<<endl; } cout<<endl; } cout<<endl; */ Clear(); } void rec() { for(int i=0;i<(1<<k);i++) { int fi=i*2; for(int j=k;j>=1;j--) { if(fi>=(1<<j)) { fi-=(1<<j); use[j]=1; } } calc(i); for(int j=1;j<=k;j++)use[j]=0; } } void read() { cin>>n>>m>>k; for(int i=1;i<=m;i++) { cin>>f[i].a>>f[i].b>>f[i].c; } for(int i=1;i<=k;i++) { cin>>l[i]>>r[i]; used[l[i]]=1; used[r[i]]=1; } for(int i=1;i<=n;i++) { cin>>br[i]; } prec(); sort(f+1,f+m+1,cmp); for(int i=1;i<=m;i++) { add1(f[i].a,f[i].b); } get_basic(); get_group(); fill_vert(); Clear(); rec(); long long int motg=0; for(int i=1;i<(1<<k);i++) { motg=max(motg,otg[i]); } cout<<motg<<endl; } int main() { speed(); read(); return 0; } /* 5 5 1 3 5 2 1 2 3 2 3 5 2 4 4 4 3 6 1 3 10 20 30 40 50 */

Compilation message (stderr)

toll.cpp: In function 'int dfs1(int, int)':
toll.cpp:160:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for(int i=0;i<vert[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
toll.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
toll.cpp: In function 'void calc(int)':
toll.cpp:213:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |         for(int j=0;j<vert[bl1].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~
#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...