# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503814 |
2022-01-08T23:49:39 Z |
tabr |
Islands (IOI08_islands) |
C++17 |
|
242 ms |
67684 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 g[N];
int deg[N + 1];
int p[N];
int l[N];
int nxt[N];
long long dist[N];
long long max_dist[N];
bool cycle[N];
bool was[N];
pair<int, long long> deq[N];
int order[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 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--;
deg[j + 1]++;
dsu_unite(i, j);
nxt[i] = j;
}
for (int i = 0; i < n; i++) {
deg[i + 1] += deg[i];
}
iota(g, g + n, 0);
sort(g, g + n, [&](int x, int y) {
if (nxt[x] == nxt[y]) {
return x < y;
}
return nxt[x] < nxt[y];
});
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;
while (u != c) {
cycle[u] = 1;
u = nxt[u];
sz++;
}
int sz2 = 0;
int beg = 0;
int end = 0;
int x = c;
for (int jj = 0; jj < sz; jj++) {
int j = x;
x = nxt[x];
deq[end++].first = j;
while (beg < end) {
int v = deq[beg++].first;
order[sz2++] = v;
for (int toid = deg[v]; toid < deg[v + 1]; toid++) {
int to = g[toid];
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);
x = nxt[c];
for (int jj = 1; jj < sz * 2; jj++) {
int j = jj % sz;
if (deq[beg].first == x) {
beg++;
}
t = max(t, y + max_dist[x] - deq[beg].second);
long long z = y - max_dist[x];
while (beg < end && deq[end - 1].second >= z) {
end--;
}
y += l[x];
deq[end++] = make_pair(j, z);
x = nxt[x];
}
ans += t;
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
4 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
5 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
6 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
7 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
8 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
9 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
11 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
972 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
3148 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
59 ms |
11656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
86 ms |
15140 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
225 ms |
55116 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
242 ms |
67684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |