# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503822 |
2022-01-09T00:20:04 Z |
tabr |
Islands (IOI08_islands) |
C++17 |
|
793 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;
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];
int p[N];
pair<int, long long> deq[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 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 |
13 ms |
23824 KB |
Output is correct |
4 |
Correct |
14 ms |
23756 KB |
Output is correct |
5 |
Correct |
12 ms |
23756 KB |
Output is correct |
6 |
Correct |
11 ms |
23756 KB |
Output is correct |
7 |
Correct |
12 ms |
23824 KB |
Output is correct |
8 |
Correct |
12 ms |
23756 KB |
Output is correct |
9 |
Correct |
12 ms |
23756 KB |
Output is correct |
10 |
Correct |
12 ms |
23868 KB |
Output is correct |
11 |
Correct |
13 ms |
23840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23820 KB |
Output is correct |
2 |
Correct |
13 ms |
23884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23884 KB |
Output is correct |
2 |
Correct |
17 ms |
24136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
24640 KB |
Output is correct |
2 |
Correct |
24 ms |
26164 KB |
Output is correct |
3 |
Correct |
19 ms |
25292 KB |
Output is correct |
4 |
Correct |
16 ms |
24524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
27076 KB |
Output is correct |
2 |
Correct |
38 ms |
29236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
37072 KB |
Output is correct |
2 |
Correct |
70 ms |
39568 KB |
Output is correct |
3 |
Correct |
89 ms |
42064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
44100 KB |
Output is correct |
2 |
Correct |
156 ms |
56900 KB |
Output is correct |
3 |
Correct |
162 ms |
65948 KB |
Output is correct |
4 |
Correct |
186 ms |
70852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
74776 KB |
Output is correct |
2 |
Correct |
502 ms |
85908 KB |
Output is correct |
3 |
Correct |
208 ms |
62116 KB |
Output is correct |
4 |
Correct |
267 ms |
82036 KB |
Output is correct |
5 |
Correct |
269 ms |
83652 KB |
Output is correct |
6 |
Correct |
793 ms |
84036 KB |
Output is correct |
7 |
Correct |
279 ms |
93460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
357 ms |
114732 KB |
Output is correct |
2 |
Correct |
286 ms |
102068 KB |
Output is correct |
3 |
Runtime error |
401 ms |
131072 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |