| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 114674 |
2019-06-02T09:29:23 Z |
zubec |
Islands (IOI08_islands) |
C++14 |
|
470 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1000100;
int n;
ll ans = 0;
int len[N], nxt[N];
vector <pair<int, int> > g[N], gg[N];
bool used[N], inCycle[N];
int used2[N], pr[N], cEnd, cStrt, pr2[N];
int cId;
int fnd_cycle(int v, int p){
used2[v] = 1;
for (int i = 0; i < gg[v].size(); i++){
int to = gg[v][i].first, id = gg[v][i].second;
if (id == p)
continue;
if (used2[to] == 0){
pr[to] = v;
pr2[to] = id;
if (fnd_cycle(to, id)){
return 1;
}
} else
if (used2[to] == 1){
cEnd = v;
cId = id;
cStrt = to;
return 1;
}
}
used2[v] = 2;
return 0;
}
ll dfs(int v, int p){
used[v] = 1;
ll curmx = 0;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i].first;
if (to == p)
continue;
curmx = max(curmx, dfs(to, v)+g[v][i].second);
}
return curmx;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
int to;
cin >> to >> len[i];
nxt[i] = to;
g[i].push_back({to, len[i]});
gg[i].push_back({to, i});
g[to].push_back({i, len[i]});
gg[to].push_back({i, i});
}
for (int i = 1; i <= n; i++){
if (used[i])
continue;
fnd_cycle(i, 0);
vector <int> cycle;
vector <ll> lens;
cycle.push_back(cStrt);
lens.push_back(0);
lens.push_back(len[cId]);
for (int v = cEnd; v != cStrt; v = pr[v]){
cId = pr2[cId];
cycle.push_back(v);
lens.push_back(len[cId]);
}
for (int j = 0; j < cycle.size(); j++){
inCycle[cycle[j]] = 1;
}
for (int j = 1; j < lens.size(); j++){
lens[j] += lens[j-1];
}
ll curans = 0;
ll mx1 = -1e18, mx2 = -1e18;
for (int j = 0; j < cycle.size(); j++){
int v = cycle[j];
used[v] = 1;
ll curmx = 0;
for (int j = 0; j < g[v].size(); j++){
int to = g[v][j].first;
if (inCycle[to])
continue;
curmx = max(curmx, dfs(to, v)+g[v][j].second);
}
curans = max(curans, curmx);
if (j == 0){
mx1 = max(mx1, curmx);
mx2 = max(mx2, curmx);
} else {
curans = max(curans, curmx+lens[j] + mx1 );
curans = max(curans, curmx+lens.back()-lens[j]+mx2 );
mx1 = max(mx1, curmx-lens[j]);
mx2 = max(mx2, curmx+lens[j]);
}
}
ans += curans;
}
cout << ans;
}
Compilation message
islands.cpp: In function 'int fnd_cycle(int, int)':
islands.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < gg[v].size(); i++){
~~^~~~~~~~~~~~~~
islands.cpp: In function 'll dfs(int, int)':
islands.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:90:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < cycle.size(); j++){
~~^~~~~~~~~~~~~~
islands.cpp:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < lens.size(); j++){
~~^~~~~~~~~~~~~
islands.cpp:101:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < cycle.size(); j++){
~~^~~~~~~~~~~~~~
islands.cpp:106:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[v].size(); j++){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
47352 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
47360 KB |
Output isn't correct |
| 3 |
Correct |
41 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
41 ms |
47360 KB |
Output is correct |
| 5 |
Correct |
43 ms |
47352 KB |
Output is correct |
| 6 |
Incorrect |
44 ms |
47480 KB |
Output isn't correct |
| 7 |
Correct |
41 ms |
47360 KB |
Output is correct |
| 8 |
Incorrect |
42 ms |
47352 KB |
Output isn't correct |
| 9 |
Correct |
41 ms |
47352 KB |
Output is correct |
| 10 |
Incorrect |
43 ms |
47356 KB |
Output isn't correct |
| 11 |
Correct |
44 ms |
47428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
47480 KB |
Output is correct |
| 2 |
Correct |
43 ms |
47480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
47608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
48888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
53560 KB |
Output is correct |
| 2 |
Correct |
93 ms |
57848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
67800 KB |
Output is correct |
| 2 |
Correct |
172 ms |
71252 KB |
Output is correct |
| 3 |
Correct |
203 ms |
81396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
85376 KB |
Output is correct |
| 2 |
Incorrect |
324 ms |
108908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
385 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
470 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
