| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 92260 | 2019-01-02T10:35:21 Z | Retro3014 | Islands (IOI08_islands) | C++17 | 527 ms | 131772 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
#define MAX_N 1000000
typedef long long ll;
int N;
struct S{
int idx;
ll data;
};
vector<S> gp[MAX_N+1];
int a, b;
struct C{
ll a, b;
};
S from[MAX_N+1];
vector<S> c;
vector<C> cycle;
bool vst[MAX_N+1];
bool isc[MAX_N+1];
int num[MAX_N+1];
ll len[MAX_N+1];
deque<int> leaf;
ll m[MAX_N+1][3];
ll ans=0;
vector<S> gp2;
int main(){
scanf("%d", &N);
for(int i=1; i<=N; i++){
scanf("%d%d", &a, &b);
gp[i].push_back((S){a, (ll)b}); num[i]++;
gp[a].push_back((S){i, (ll)b}); num[a]++;
}
for(int i=1; i<=N; i++){
if(num[i]==1){
leaf.push_back(i);
}
}
while(!leaf.empty()){
int now=leaf.front(); leaf.pop_front();
vst[now]=true;
m[now][0]=max(m[now][0], m[now][1]+m[now][2]);
for(int i=0; i<gp[now].size(); i++){
if(!vst[gp[now][i].idx]){
len[gp[now][i].idx]=max(len[gp[now][i].idx], len[now]+gp[now][i].data);
m[gp[now][i].idx][0]=max(m[gp[now][i].idx][0], m[now][0]);
if(len[now]+gp[now][i].data>m[gp[now][i].idx][1]){
m[gp[now][i].idx][2]=m[gp[now][i].idx][1];
m[gp[now][i].idx][1]=len[now]+gp[now][i].data;
}else if(len[now]+gp[now][i].data>m[gp[now][i].idx][2]){
m[gp[now][i].idx][2]=len[now]+gp[now][i].data;
}
num[gp[now][i].idx]--;
if(num[gp[now][i].idx]==1){
leaf.push_back(gp[now][i].idx);
}
}
}
}
for(int i=1; i<=N; i++){
if(!vst[i]){
for(int j=0; j<gp[i].size(); j++){
if(!vst[gp[i][j].idx]){
gp2.push_back(gp[i][j]);
}
}
while(!gp[i].empty()) gp[i].pop_back();
while(!gp2.empty()){
gp[i].push_back(gp2.back()); gp2.pop_back();
}
}
}
for(int i=1; i<=N; i++){
if(!vst[i]){
c.push_back({gp[i][1].idx, gp[i][1].data});
int t=i;
while(!c.empty()){
vst[t]=true;
if(vst[gp[t][0].idx]){
if(vst[gp[t][1].idx]){
break;
}
c.push_back({t, gp[t][1].data});
t=gp[t][1].idx;
}else{
c.push_back({t, gp[t][0].data});
t=gp[t][0].idx;
}
}
ll ans2=0;
ll sum=0;
while(!c.empty()){
S now = c.back(); c.pop_back();
ans2=max(ans2, m[now.idx][0]);
sum+=now.data;
cycle.push_back({now.data, len[now.idx]});
}
ll m1=0, m2=0;
while(!cycle.empty()){
C now = cycle.back(); cycle.pop_back();
ans2=max(ans2, max(now.b, max(m1+now.b, m2+now.b)));
m1=max(m1+now.a, now.a+now.b);
m2=max(m2-now.a, sum-now.a+now.b);
}
ans+=ans2;
}
}
printf("%lld", ans);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 23800 KB | Output is correct |
| 2 | Correct | 23 ms | 23928 KB | Output is correct |
| 3 | Correct | 22 ms | 23800 KB | Output is correct |
| 4 | Correct | 22 ms | 23800 KB | Output is correct |
| 5 | Correct | 22 ms | 23800 KB | Output is correct |
| 6 | Correct | 22 ms | 23800 KB | Output is correct |
| 7 | Correct | 22 ms | 23800 KB | Output is correct |
| 8 | Correct | 22 ms | 23800 KB | Output is correct |
| 9 | Correct | 22 ms | 23800 KB | Output is correct |
| 10 | Incorrect | 23 ms | 23928 KB | Output isn't correct |
| 11 | Correct | 22 ms | 23928 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 23 ms | 23928 KB | Output is correct |
| 2 | Correct | 22 ms | 23928 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 24 ms | 24056 KB | Output is correct |
| 2 | Correct | 26 ms | 24352 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 31 ms | 25592 KB | Output is correct |
| 2 | Correct | 45 ms | 28184 KB | Output is correct |
| 3 | Correct | 31 ms | 26052 KB | Output is correct |
| 4 | Correct | 25 ms | 24952 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 54 ms | 30084 KB | Output is correct |
| 2 | Correct | 64 ms | 33516 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 120 ms | 43632 KB | Output is correct |
| 2 | Correct | 118 ms | 44040 KB | Output is correct |
| 3 | Correct | 146 ms | 56472 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 193 ms | 58076 KB | Output is correct |
| 2 | Correct | 260 ms | 80128 KB | Output is correct |
| 3 | Correct | 277 ms | 69000 KB | Output is correct |
| 4 | Correct | 322 ms | 102040 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 397 ms | 104196 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 427 ms | 107600 KB | Output is correct |
| 2 | Correct | 457 ms | 107384 KB | Output is correct |
| 3 | Runtime error | 527 ms | 131772 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 4 | Halted | 0 ms | 0 KB | - |