Submission #201181

#TimeUsernameProblemLanguageResultExecution timeMemory
201181a_playerIslands (IOI08_islands)C++14
0 / 100
2096 ms23928 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]; ll m[MAXN][4]; deque<int> cyc; ll succ[MAXN]; bitset<MAXN> v; bitset<MAXN> k; ll zipp[MAXN]; 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[cyc[0]][0]=0; for(int i=1;i<se;i++)m[cyc[i]][0]=m[cyc[i-1]][0]+succ[cyc[i-1]]; m[cyc[0]][1]=zipp[cyc[0]]; for(int i=1;i<se;i++)m[cyc[i]][1]=max(m[cyc[i-1]][1],m[cyc[i]][0]+zipp[cyc[i]]); m[cyc.back()][2]=0; for(int i=se-2;i>=0;i--)m[cyc[i]][2]=m[cyc[i+1]][2]+succ[cyc[i]]; m[cyc.back()][3]=zipp[cyc.back()]; for(int i=se-2;i>=0;i--)m[cyc[i]][3]=max(m[cyc[i+1]][3],m[cyc[i]][2]+zipp[cyc[i]]); ll ans=0; for(int i=0;i<se-1;i++)ans=max(ans,m[cyc[i]][1]+m[cyc[i+1]][3]+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); out<<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++)
                 ~^~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:141:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...