# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
217694 | 2020-03-30T12:44:08 Z | mhy908 | Islands (IOI08_islands) | C++14 | 1124 ms | 131072 KB |
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define F first #define S second using namespace std; typedef long LL; typedef pair<int, int> pii; const LL llinf=1987654321987654321; int n; LL ret, ans; vector<pii> link[1000010]; int cyc[800010], re; LL sum[800010]; bool ch[1000010]; inline LL get_cyc(int num, int par){ if(ch[num]){ cyc[re]=num; sum[re++]=0; return 0; } ch[num]=true; bool t=true; for(pii i:link[num]){ if(i.F==par&&t){ t=false; continue; } LL temp=get_cyc(i.F, num)+i.S; if(temp>=0){ ch[num]=false; cyc[re]=num; sum[re++]=temp; if(cyc[0]==num)return -llinf; return temp; } } ch[num]=false; return -llinf; } inline LL get_maxd(int num, int par1, int par2){ LL ret2=0; ch[num]=true; for(pii i:link[num]){ if(i.F==par1||i.F==par2)continue; LL temp=get_maxd(i.F, num, num)+i.S; ret=max(ret, ret2+temp); ret2=max(ret2, temp); } return ret2; } int main(){ scanf("%d", &n); for(int i=1; i<=n; i++){ int a, b; scanf("%d %d", &a, &b); link[i].pb(mp(a, b)); link[a].pb(mp(i, b)); } for(int j=1; j<=n; j++){ if(ch[j])continue; re=0; ret=0; get_cyc(j, 0); LL max1=llinf, max2=-llinf, dia=sum[--re]; for(int i=0; i<re; i++){ LL tmp=get_maxd(cyc[i], cyc[(i+re-1)%re], cyc[(i+1)%re]); ret=max(ret, sum[i]+tmp-max1); ret=max(ret, dia-sum[i]+tmp+max2); max2=max(max2, sum[i]+tmp); max1=min(max1, sum[i]-tmp); } ans+=ret; } printf("%lld", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 23808 KB | Output is correct |
2 | Correct | 18 ms | 23808 KB | Output is correct |
3 | Correct | 17 ms | 23936 KB | Output is correct |
4 | Correct | 17 ms | 23808 KB | Output is correct |
5 | Correct | 20 ms | 23808 KB | Output is correct |
6 | Correct | 17 ms | 23808 KB | Output is correct |
7 | Correct | 18 ms | 23808 KB | Output is correct |
8 | Correct | 17 ms | 23808 KB | Output is correct |
9 | Correct | 17 ms | 23808 KB | Output is correct |
10 | Correct | 17 ms | 23808 KB | Output is correct |
11 | Correct | 17 ms | 23808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 23936 KB | Output is correct |
2 | Correct | 19 ms | 23808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23936 KB | Output is correct |
2 | Correct | 24 ms | 24064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 24440 KB | Output is correct |
2 | Correct | 37 ms | 26032 KB | Output is correct |
3 | Correct | 29 ms | 24676 KB | Output is correct |
4 | Correct | 24 ms | 24168 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 26872 KB | Output is correct |
2 | Correct | 61 ms | 28456 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 111 ms | 32504 KB | Output is correct |
2 | Correct | 121 ms | 35320 KB | Output is correct |
3 | Correct | 159 ms | 41464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 197 ms | 39280 KB | Output is correct |
2 | Correct | 231 ms | 53672 KB | Output is correct |
3 | Correct | 259 ms | 57080 KB | Output is correct |
4 | Correct | 315 ms | 68600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 426 ms | 63952 KB | Output is correct |
2 | Correct | 765 ms | 88556 KB | Output is correct |
3 | Correct | 368 ms | 54904 KB | Output is correct |
4 | Correct | 479 ms | 77816 KB | Output is correct |
5 | Correct | 439 ms | 78456 KB | Output is correct |
6 | Correct | 1124 ms | 59972 KB | Output is correct |
7 | Correct | 481 ms | 93560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 502 ms | 95992 KB | Output is correct |
2 | Correct | 477 ms | 77280 KB | Output is correct |
3 | Runtime error | 587 ms | 131072 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
4 | Halted | 0 ms | 0 KB | - |