Submission #201186

#TimeUsernameProblemLanguageResultExecution timeMemory
201186a_playerIslands (IOI08_islands)C++14
70 / 100
659 ms131076 KiB
#include <bits/stdc++.h> #define f first #define s second.first #define tr second.second #define mp make_pair using namespace std; //ofstream out("output.txt"); const int MAXN =1e6+1; typedef long long ll; int read(){ int r=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); r=ch-'0'; ch=getchar(); while(ch>='0'&&ch<='9'){ r=r*10+ch-'0'; ch=getchar(); } return r; } vector<pair<int,pair<ll,int> > > grafo[MAXN]; map<int,ll> m[4]; deque<int> cyc; map<int,ll> succ; bitset<MAXN> v; bitset<MAXN> k; map<int,ll> zipp; int pos[MAXN]; bool find_cyc(int n, int pa){ v[n]=1; k[n]=1; cyc.push_back(n); for(auto x:grafo[n]){ if(!v[x.f]){ if(find_cyc(x.f,x.tr))return true; } else if(x.tr!=pa){ cyc.push_back(x.f); return true; } } cyc.pop_back(); return false; } ll zip(int n, int a, int b, int c){ k[n]=1; ll mas=0; for(auto x:grafo[n]){ if(x.f==a||x.f==b||x.f==c)continue; mas=max(mas,zip(x.f,n,b,c)+x.s); } return mas; } ll dfs(int n, int a){ ll mas=0; pos[n]=-1; k[n]=1; for(auto x:grafo[n]){ if(n==cyc.front()&&x.f==cyc.back())continue; if(x.f==cyc.front()&&n==cyc.back())continue; if(x.f==a)continue; ll p=dfs(x.f,n)+x.s; if(mas<p){ mas=p; pos[n]=pos[x.f]; } } if(pos[n]==-1)pos[n]=n; return mas; } ll dfs2(int n, int a, int w){ ll mas=0; pos[n]=-1; k[n]=1; for(auto x:grafo[n]){ if(n==cyc.front()&&x.f==cyc.back()&&x.s!=w)continue; if(x.f==cyc.front()&&n==cyc.back()&&x.s!=w)continue; if(x.f==a)continue; ll p=dfs2(x.f,n,w)+x.s; if(mas<p){ mas=p; pos[n]=pos[x.f]; } } if(pos[n]==-1)pos[n]=n; return mas; } int N; ll process(int t){ cyc.clear(); find_cyc(t,-1); while(cyc.front()!=cyc.back())cyc.pop_front(); cyc.pop_front(); zipp[cyc[0]]=zip(cyc[0],-1,cyc[1],cyc.back()); for(int i=1;i<cyc.size()-1;i++)zipp[cyc[i]]=zip(cyc[i],-1,cyc[i-1],cyc[i+1]); zipp[cyc.back()]=zip(cyc.back(),-1,cyc[cyc.size()-2],cyc.front()); if(cyc.size()==2){ ll mass=0; for(auto x:grafo[cyc[0]]) if(x.f==cyc[1]){ mass=max(mass,x.s); } dfs2(t,-1,mass); return dfs2(pos[t],-1,mass); } for(int i=1;i<cyc.size()-1;i++) for(auto x:grafo[cyc[i]]) if(x.f==cyc[i+1]){ succ[cyc[i]]=x.s; break; } ll speciale=0; for(auto x:grafo[cyc[0]]){ if(x.f==cyc[1])succ[cyc[0]]=x.s; if(x.f==cyc.back())speciale=x.s; } int se=cyc.size(); m[0][cyc[0]]=0; for(int i=1;i<se;i++)m[0][cyc[i]]=m[0][cyc[i-1]]+succ[cyc[i-1]]; m[1][cyc[0]]=zipp[cyc[0]]; for(int i=1;i<se;i++)m[1][cyc[i]]=max(m[1][cyc[i-1]],m[0][cyc[i]]+zipp[cyc[i]]); m[2][cyc.back()]=0; for(int i=se-2;i>=0;i--)m[2][cyc[i]]=m[2][cyc[i+1]]+succ[cyc[i]]; m[3][cyc.back()]=zipp[cyc.back()]; for(int i=se-2;i>=0;i--)m[3][cyc[i]]=max(m[3][cyc[i+1]],m[2][cyc[i]]+zipp[cyc[i]]); ll ans=0; for(int i=0;i<se-1;i++)ans=max(ans,m[1][cyc[i]]+m[3][cyc[i+1]]+speciale); dfs(t,-1); ans=max(ans,dfs(pos[t],-1)); return ans; } int main(){ //freopen("input.txt","r",stdin); N=read(); for(int i=0;i<N;i++){ int a,c; a=read(),c=read(); a--; grafo[a].push_back(mp(i,mp((ll)c,i))); grafo[i].push_back(mp(a,mp((ll)c,i))); } ll ans=0; for(int i=0;i<N;i++) if(!k[i])ans+=process(i); cout<<ans; }

Compilation message (stderr)

islands.cpp: In function 'll process(int)':
islands.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cyc.size()-1;i++)zipp[cyc[i]]=zip(cyc[i],-1,cyc[i-1],cyc[i+1]);
                 ~^~~~~~~~~~~~~
islands.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cyc.size()-1;i++)
                 ~^~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...