| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 114730 |
2019-06-02T12:48:11 Z |
zubec |
Islands (IOI08_islands) |
C++14 |
|
1729 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1000010;
int n;
ll ans = 0;
int len[N], nxt[N];
vector <int> g[N];
bool block[N];
int used[N], cEnd, cStrt, pr2[N];
int cId;
int getTo(int v, int id){
return (v == id ? nxt[v] : id);
}
int fnd_cycle(int v, int p){
used[v] = 1;
for (int i = 0; i < g[v].size(); i++){
int id = g[v][i];
int to = getTo(v, id);
if (id == p)
continue;
if (used[to] == 0){
pr2[to] = id;
if (fnd_cycle(to, id)){
return 1;
}
} else
if (used[to] == 1){
cEnd = v;
cId = id;
cStrt = to;
return 1;
}
}
used[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 id = g[v][i];
int to = getTo(v, id);
if (to == p)
continue;
curmx = max(curmx, dfs(to, v)+len[id]);
}
return curmx;
}
ll mx, mxver;
void dfs2(int v, int p, ll curlen){
if (curlen > mx){
mx = curlen;
mxver = v;
}
for (int i = 0; i < g[v].size(); i++){
int id = g[v][i];
int to = getTo(v, id);
if (!block[id] && to != p)
dfs2(to, v, curlen+len[id]);
}
}
ll fnd_diam(int v){
mx = -1, mxver = 0;
dfs2(v, 0, 0);
mx = -1;
dfs2(mxver, 0, 0);
return mx;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> nxt[i] >> len[i];
g[i].push_back(i);
g[nxt[i]].push_back(i);
}
for (int i = 1; i <= n; i++){
if (used[i])
continue;
fnd_cycle(i, 0);
vector <int> cycle;
vector <int> lens;
cycle.push_back(cStrt);
lens.push_back(0);
lens.push_back(len[cId]);
ll sumLens = len[cId];
block[cId] = 1;
for (int v = cEnd; v != cStrt;){
cId = pr2[v];
cycle.push_back(v);
v = getTo(v, cId);
lens.push_back(len[cId]);
sumLens += len[cId];
block[cId] = 1;
}
ll curans = 0;
ll mx1 = -1e18, mx2 = -1e18;
ll curLen = 0;
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 id = g[v][j];
int to = getTo(v, id);
if (block[id])
continue;
curmx = max(curmx, dfs(to, v)+len[id]);
}
curans = max(curans, curmx);
curans = max(curans, fnd_diam(v));
if (j == 0){
mx1 = max(mx1, curmx);
mx2 = max(mx2, curmx);
} else {
curLen += lens[j];
curans = max(curans, curmx+curLen+ mx1 );
curans = max(curans, curmx+sumLens-curLen + mx2 );
mx1 = max(mx1, curmx-curLen);
mx2 = max(mx2, curmx+curLen);
}
}
ans += curans;
}
cout << ans;
}
Compilation message
islands.cpp: In function 'int fnd_cycle(int, int)':
islands.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
islands.cpp: In function 'll dfs(int, int)':
islands.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
islands.cpp: In function 'void dfs2(int, int, ll)':
islands.cpp:73: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:126:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < cycle.size(); j++){
~~^~~~~~~~~~~~~~
islands.cpp:131: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 |
22 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23936 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23808 KB |
Output is correct |
| 7 |
Correct |
21 ms |
23808 KB |
Output is correct |
| 8 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 9 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 11 |
Correct |
23 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
29 ms |
24196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
24732 KB |
Output is correct |
| 2 |
Correct |
42 ms |
26488 KB |
Output is correct |
| 3 |
Correct |
37 ms |
24960 KB |
Output is correct |
| 4 |
Correct |
29 ms |
24312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
27480 KB |
Output is correct |
| 2 |
Correct |
58 ms |
29748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
34920 KB |
Output is correct |
| 2 |
Correct |
278 ms |
39292 KB |
Output is correct |
| 3 |
Correct |
162 ms |
44652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
44012 KB |
Output is correct |
| 2 |
Correct |
217 ms |
59168 KB |
Output is correct |
| 3 |
Correct |
243 ms |
67900 KB |
Output is correct |
| 4 |
Correct |
274 ms |
75868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
337 ms |
73464 KB |
Output is correct |
| 2 |
Correct |
852 ms |
97676 KB |
Output is correct |
| 3 |
Correct |
303 ms |
63436 KB |
Output is correct |
| 4 |
Correct |
421 ms |
87660 KB |
Output is correct |
| 5 |
Correct |
395 ms |
87308 KB |
Output is correct |
| 6 |
Correct |
1729 ms |
70520 KB |
Output is correct |
| 7 |
Correct |
437 ms |
105948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
