# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503824 |
2022-01-09T00:24:26 Z |
tabr |
Islands (IOI08_islands) |
C++17 |
|
779 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
const int N = (int) 1e6 + 100;
int p[N];
int dsu_get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = dsu_get(p[x]);
}
}
bool dsu_unite(int x, int y) {
x = dsu_get(x);
y = dsu_get(y);
if (x == y) {
return false;
}
p[x] = y;
return true;
}
int l[N];
int nxt[N];
long long dist[N];
long long max_dist[N];
bool cycle[N];
bool was[N];
vector<int> g[N];
pair<int, long long> deq[N];
int x[N];
int order[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
iota(p, p + n, 0);
for (int i = 0; i < n; i++) {
int j;
cin >> j >> l[i];
j--;
g[j].emplace_back(i);
dsu_unite(i, j);
nxt[i] = j;
}
long long ans = 0;
for (int i = 0; i < n; i++) {
if (i != dsu_get(i)) {
continue;
}
int c = i;
while (!was[c]) {
was[c] = 1;
c = nxt[c];
}
int u = nxt[c];
cycle[c] = 1;
int sz = 1;
x[0] = c;
while (u != c) {
cycle[u] = 1;
x[sz++] = u;
u = nxt[u];
}
int sz2 = 0;
int beg = 0;
int end = 0;
for (int jj = 0; jj < sz; jj++) {
int j = x[jj];
deq[end++].first = j;
while (beg < end) {
int v = deq[beg++].first;
order[sz2++] = v;
for (int to : g[v]) {
if (cycle[to]) {
continue;
}
dist[to] = dist[v] + l[to];
deq[end++].first = to;
}
}
}
long long t = 0;
for (int j = sz2 - 1; j >= 0; j--) {
int v = order[j];
max_dist[v] = max(max_dist[v], dist[v]);
if (cycle[v]) {
continue;
}
int to = nxt[v];
t = max(t, max_dist[to] + max_dist[v] - dist[to] * 2);
max_dist[to] = max(max_dist[to], max_dist[v]);
}
long long y = l[c];
beg = end = 0;
deq[end++] = make_pair(0, 0);
for (int jj = 1; jj < sz * 2; jj++) {
int j = jj % sz;
if (x[deq[beg].first] == x[j]) {
beg++;
}
t = max(t, y + max_dist[x[j]] - deq[beg].second);
long long z = y - max_dist[x[j]];
while (beg < end && deq[end - 1].second >= z) {
end--;
}
y += l[x[j]];
deq[end++] = make_pair(j, z);
}
ans += t;
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23756 KB |
Output is correct |
2 |
Correct |
12 ms |
23884 KB |
Output is correct |
3 |
Correct |
12 ms |
23884 KB |
Output is correct |
4 |
Correct |
11 ms |
23744 KB |
Output is correct |
5 |
Correct |
11 ms |
23756 KB |
Output is correct |
6 |
Correct |
11 ms |
23812 KB |
Output is correct |
7 |
Correct |
11 ms |
23756 KB |
Output is correct |
8 |
Correct |
11 ms |
23856 KB |
Output is correct |
9 |
Correct |
13 ms |
23756 KB |
Output is correct |
10 |
Correct |
11 ms |
23884 KB |
Output is correct |
11 |
Correct |
11 ms |
23872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23924 KB |
Output is correct |
2 |
Correct |
12 ms |
23884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23916 KB |
Output is correct |
2 |
Correct |
13 ms |
24140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26060 KB |
Output is correct |
3 |
Correct |
22 ms |
25292 KB |
Output is correct |
4 |
Correct |
14 ms |
24560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
27092 KB |
Output is correct |
2 |
Correct |
37 ms |
29248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
37172 KB |
Output is correct |
2 |
Correct |
72 ms |
39640 KB |
Output is correct |
3 |
Correct |
88 ms |
42136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
44108 KB |
Output is correct |
2 |
Correct |
160 ms |
56824 KB |
Output is correct |
3 |
Correct |
146 ms |
65876 KB |
Output is correct |
4 |
Correct |
202 ms |
70888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
251 ms |
74732 KB |
Output is correct |
2 |
Correct |
560 ms |
85816 KB |
Output is correct |
3 |
Correct |
204 ms |
62080 KB |
Output is correct |
4 |
Correct |
287 ms |
81988 KB |
Output is correct |
5 |
Correct |
272 ms |
83792 KB |
Output is correct |
6 |
Correct |
779 ms |
84228 KB |
Output is correct |
7 |
Runtime error |
378 ms |
131072 KB |
Execution killed with signal 11 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
298 ms |
114596 KB |
Output is correct |
2 |
Correct |
286 ms |
102088 KB |
Output is correct |
3 |
Runtime error |
401 ms |
131072 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |