# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
219140 | 2020-04-03T20:43:56 Z | peuch | Islands (IOI08_islands) | C++17 | 1192 ms | 131076 KB |
#include<bits/stdc++.h> using namespace std; const int MAXN = 1000010; int n; int rep; int in[MAXN]; long long prof[MAXN], dist[MAXN]; vector<int> ar[MAXN], wg[MAXN]; bool isCycle[MAXN], marc[MAXN]; long long ans; void getCycle(); int dfs1(int cur){ marc[cur] = 1; int ret = cur; for(int i = 0; i < ar[cur].size(); i++){ int viz = ar[cur][i]; if(in[viz]) continue; if(marc[viz]) continue; dist[viz] = dist[cur] + wg[cur][i]; int aux = dfs1(viz); if(dist[aux] > dist[ret]) ret = aux; } return ret; } long long dfs2(int cur){ marc[cur] = 0; long long ret = dist[cur]; for(int i = 0; i < ar[cur].size(); i++){ int viz = ar[cur][i]; if(isCycle[viz] && viz != rep) continue; if(!marc[viz]) continue; dist[viz] = dist[cur] + wg[cur][i]; ret = max(ret, dfs2(viz)); } return ret; } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ int aux1, aux2; scanf("%d %d", &aux1, &aux2); in[aux1]++; ar[aux1].push_back(i); ar[i].push_back(aux1); wg[i].push_back(aux2); wg[aux1].push_back(aux2); } getCycle(); printf("%lld\n", ans); } void getCycle(){ int fila[n]; int fim = 0; int ini = 0; for(int i = 1; i <= n; i++) if(in[i] == 0) fila[fim++] = i; while(ini != fim){ int cur = fila[ini++]; for(int j = 0; j < ar[cur].size(); j++){ int viz = ar[cur][j]; if(in[viz] == 0) continue; in[viz]--; prof[viz] = max(prof[viz], prof[cur] + wg[cur][j]); if(in[viz] == 0) fila[fim++] = viz; } } for(int i = 1; i <= n; i++){ if(!in[i] || isCycle[i]) continue; int cur = i; dist[cur] = 0; int cnt = 0; int last = 0; long long aux = 0; long long sct = 0; while(1){ last = cur; cnt++; isCycle[cur] = 1; rep = cur; long long auxDist = dist[cur]; dist[cur] = 0; int x = dfs1(cur); dist[x] = 0; aux = max(aux, dfs2(x)); dist[cur] = auxDist; bool flag = true; for(int j = 0; j < ar[cur].size(); j++){ int viz = ar[cur][j]; if(!in[viz] || isCycle[viz]) continue; dist[viz] = dist[cur] + wg[cur][j]; sct += wg[cur][i]; cur = viz; flag = false; break; } if(flag) break; } if(cnt == 1){ ans += aux; continue; } if(cnt == 2){ sct = 0; for(int j = 0; j < ar[i].size(); j++) if(isCycle[ar[i][j]]) sct += wg[i][j]; } else{ for(int j = 0; j < ar[cur].size(); j++) if(ar[cur][j] == i) sct += wg[i][j]; } long long aux2 = prof[cur] + dist[cur]; long long aux3 = prof[cur] - dist[cur]; if(cnt == 2) cur = i; else{ for(int j = 0; j < ar[cur].size(); j++) { int viz = ar[cur][j]; if(!isCycle[viz]) continue; if(dist[viz] > dist[cur] || viz == i) continue; cur = viz; break; } } while(1){ aux = max(aux, aux2 + prof[cur] - dist[cur]); aux = max(aux, aux3 + sct + prof[cur] + dist[cur]); aux2 = max(aux2, prof[cur] + dist[cur]); aux3 = max(aux3, prof[cur] - dist[cur]); bool flag = true; for(int j = 0; j < ar[cur].size(); j++) { int viz = ar[cur][j]; if(!isCycle[viz]) continue; if(dist[viz] > dist[cur]) continue; cur = viz; flag = false; break; } if(flag) break; } if(cnt == 2) cur = last; else{ for(int j = 0; j < ar[cur].size(); j++) { int viz = ar[cur][j]; if(!isCycle[viz]) continue; if(dist[viz] < dist[cur] || viz == last) continue; cur = viz; break; } } aux2 = prof[i] - dist[i]; aux3 = prof[i] + dist[i]; while(1){ if(cur == i) break; aux = max(aux, aux2 + prof[cur] + dist[cur]); aux = max(aux, aux3 + sct + prof[cur] - dist[cur]); aux2 = max(aux2, prof[cur] - dist[cur]); aux3 = max(aux3, prof[cur] + dist[cur]); bool flag = true; for(int j = 0; j < ar[cur].size(); j++) { int viz = ar[cur][j]; if(!isCycle[viz]) continue; if(dist[viz] < dist[cur]) continue; cur = viz; flag = false; break; } if(flag) break; } ans += aux; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 47360 KB | Output is correct |
2 | Incorrect | 30 ms | 47352 KB | Output isn't correct |
3 | Incorrect | 30 ms | 47360 KB | Output isn't correct |
4 | Correct | 31 ms | 47488 KB | Output is correct |
5 | Incorrect | 29 ms | 47360 KB | Output isn't correct |
6 | Correct | 29 ms | 47360 KB | Output is correct |
7 | Incorrect | 31 ms | 47352 KB | Output isn't correct |
8 | Incorrect | 31 ms | 47352 KB | Output isn't correct |
9 | Incorrect | 30 ms | 47360 KB | Output isn't correct |
10 | Correct | 30 ms | 47360 KB | Output is correct |
11 | Correct | 30 ms | 47352 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 47352 KB | Output is correct |
2 | Correct | 31 ms | 47476 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 47488 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 48 ms | 48872 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 67 ms | 52344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 181 ms | 67680 KB | Output is correct |
2 | Runtime error | 218 ms | 131072 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 394 ms | 131072 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 499 ms | 131072 KB | Output is correct |
2 | Incorrect | 1192 ms | 131072 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 562 ms | 131076 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |