| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 201182 |
2020-02-09T15:50:55 Z |
a_player |
Islands (IOI08_islands) |
C++14 |
|
645 ms |
131076 KB |
#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);
cout<<ans;
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
21 ms |
23928 KB |
Output is correct |
| 4 |
Correct |
21 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
21 ms |
23800 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 8 |
Correct |
25 ms |
23928 KB |
Output is correct |
| 9 |
Correct |
20 ms |
23960 KB |
Output is correct |
| 10 |
Correct |
21 ms |
23800 KB |
Output is correct |
| 11 |
Correct |
20 ms |
23800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
24184 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
25976 KB |
Output is correct |
| 2 |
Correct |
41 ms |
29944 KB |
Output is correct |
| 3 |
Correct |
32 ms |
26616 KB |
Output is correct |
| 4 |
Correct |
27 ms |
25212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
32440 KB |
Output is correct |
| 2 |
Correct |
60 ms |
38648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
51448 KB |
Output is correct |
| 2 |
Correct |
128 ms |
55800 KB |
Output is correct |
| 3 |
Correct |
165 ms |
72312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
189 ms |
77176 KB |
Output is correct |
| 2 |
Correct |
262 ms |
108092 KB |
Output is correct |
| 3 |
Correct |
299 ms |
119160 KB |
Output is correct |
| 4 |
Runtime error |
308 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
363 ms |
98412 KB |
Output is correct |
| 2 |
Runtime error |
645 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
382 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
