# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503827 |
2022-01-09T00:37:46 Z |
tabr |
Islands (IOI08_islands) |
C++17 |
|
864 ms |
104912 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct dsu {
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
inline int get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = get(p[x]);
}
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
if (sz[x] > sz[y]) {
swap(x, y);
}
p[x] = y;
sz[y] += sz[x];
return true;
}
inline bool same(int x, int y) {
return (get(x) == get(y));
}
};
const int N = (int) 1e6 + 10;
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 main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
dsu uf(n);
for (int i = 0; i < n; i++) {
int j;
cin >> j >> l[i];
j--;
g[j].emplace_back(i);
uf.unite(i, j);
nxt[i] = j;
}
long long ans = 0;
queue<int> que;
deque<pair<int, long long>> deq;
for (int i = 0; i < n; i++) {
if (i != uf.get(i)) {
continue;
}
int c = i;
while (!was[c]) {
was[c] = 1;
c = nxt[c];
}
int u = nxt[c];
cycle[c] = 1;
vector<int> x(1, c);
while (u != c) {
cycle[u] = 1;
x.emplace_back(u);
u = nxt[u];
}
vector<int> order;
for (int j : x) {
que.emplace(j);
while (!que.empty()) {
int v = que.front();
order.emplace_back(v);
que.pop();
for (int to : g[v]) {
if (cycle[to]) {
continue;
}
dist[to] = dist[v] + l[to];
que.emplace(to);
}
}
}
long long t = 0;
reverse(order.begin(), order.end());
for (int v : order) {
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]);
}
deq.emplace_back(0, 0);
long long y = l[c];
int sz = (int) x.size();
for (int jj = 1; jj < sz * 2; jj++) {
int j = jj % sz;
if (x[deq.front().first] == x[j]) {
deq.pop_front();
}
t = max(t, y + max_dist[x[j]] - deq.front().second);
long long z = y - max_dist[x[j]];
while (!deq.empty() && deq.back().second >= z) {
deq.pop_back();
}
y += l[x[j]];
deq.emplace_back(j, z);
}
deq.clear();
ans += t;
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23756 KB |
Output is correct |
2 |
Correct |
11 ms |
23756 KB |
Output is correct |
3 |
Correct |
13 ms |
23768 KB |
Output is correct |
4 |
Correct |
11 ms |
23756 KB |
Output is correct |
5 |
Correct |
11 ms |
23840 KB |
Output is correct |
6 |
Correct |
11 ms |
23772 KB |
Output is correct |
7 |
Correct |
13 ms |
23756 KB |
Output is correct |
8 |
Correct |
11 ms |
23756 KB |
Output is correct |
9 |
Correct |
14 ms |
23824 KB |
Output is correct |
10 |
Correct |
12 ms |
23756 KB |
Output is correct |
11 |
Correct |
12 ms |
23748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23884 KB |
Output is correct |
2 |
Correct |
12 ms |
23884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23884 KB |
Output is correct |
2 |
Correct |
12 ms |
23988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
24724 KB |
Output is correct |
2 |
Correct |
22 ms |
25944 KB |
Output is correct |
3 |
Correct |
19 ms |
25044 KB |
Output is correct |
4 |
Correct |
15 ms |
24440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
26764 KB |
Output is correct |
2 |
Correct |
36 ms |
29472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
35024 KB |
Output is correct |
2 |
Correct |
73 ms |
38932 KB |
Output is correct |
3 |
Correct |
86 ms |
40892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
45440 KB |
Output is correct |
2 |
Correct |
143 ms |
51356 KB |
Output is correct |
3 |
Correct |
153 ms |
64368 KB |
Output is correct |
4 |
Correct |
189 ms |
67688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
67072 KB |
Output is correct |
2 |
Correct |
503 ms |
80524 KB |
Output is correct |
3 |
Correct |
220 ms |
65104 KB |
Output is correct |
4 |
Correct |
293 ms |
79484 KB |
Output is correct |
5 |
Correct |
277 ms |
76396 KB |
Output is correct |
6 |
Correct |
826 ms |
77056 KB |
Output is correct |
7 |
Correct |
301 ms |
91412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
91340 KB |
Output is correct |
2 |
Correct |
283 ms |
90716 KB |
Output is correct |
3 |
Correct |
294 ms |
104912 KB |
Output is correct |
4 |
Correct |
334 ms |
80492 KB |
Output is correct |
5 |
Correct |
283 ms |
79096 KB |
Output is correct |
6 |
Correct |
273 ms |
82308 KB |
Output is correct |
7 |
Correct |
864 ms |
80004 KB |
Output is correct |