| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 548446 |
2022-04-13T12:34:54 Z |
Temmie |
Islands (IOI08_islands) |
C++17 |
|
1504 ms |
131072 KB |
#include <bits/stdc++.h>
struct Seg {
std::vector <long long> m, v, w;
int size;
Seg(int s) {
size = 1;
while (size < s) {
size <<= 1;
}
m.resize(size << 1, 0);
v.resize(size << 1, 0);
w.resize(size << 1, 0);
}
void update(int l, int r, long long delta) {
update(l, r, delta, 0, 0, size);
}
void update(int tl, int tr, long long delta, int now, int l, int r) {
push(now, l, r);
if (l >= tr || r <= tl) {
return;
}
if (l >= tl && r <= tr) {
w[now] += delta;
push(now, l, r);
return;
}
int mid = (l + r) >> 1;
update(tl, tr, delta, now * 2 + 1, l, mid);
update(tl, tr, delta, now * 2 + 2, mid, r);
v[now] = v[now * 2 + 1] + v[now * 2 + 2];
m[now] = std::max(m[now * 2 + 1], m[now * 2 + 2]);
}
long long query(int l, int r) {
return query(l, r, 0, 0, size);
}
bool outside(int l, int r, int tl, int tr) {
return l >= tr || r <= tl;
}
long long query(int tl, int tr, int now, int l, int r) {
push(now, l, r);
if (l >= tl && r <= tr) {
return m[now];
}
int mid = (l + r) >> 1;
long long ret = 0;
if (outside(l, mid, tl, tr)) {
ret = query(tl, tr, (now << 1) + 2, mid, r);
} else {
if (outside(mid, r, tl, tr)) {
ret = query(tl, tr, (now << 1) + 1, l, mid);
} else {
ret = std::max(
query(tl, tr, (now << 1) + 1, l, mid),
query(tl, tr, (now << 1) + 2, mid, r));
}
}
return ret;
}
void push(int node, int l, int r) {
v[node] += w[node] * (r - l);
m[node] += w[node];
if (r - l - 1) {
w[node * 2 + 1] += w[node];
w[node * 2 + 2] += w[node];
}
w[node] = 0;
}
};
int n;
std::vector <std::vector <std::pair <int, std::pair <int, int>>>> g;
std::vector <std::vector <int>> c;
std::vector <int> cc;
std::vector <long long> cans;
void fc(int node, std::vector <bool>& vis) {
if (vis[node]) {
return;
}
vis[node] = true;
c.back().push_back(node);
for (auto p : g[node]) {
fc(p.second.first, vis);
}
}
std::vector <bool> cyc;
bool cy(int node, int par, std::vector <bool>& vis) {
if (vis[node]) {
return cyc[node] = true;
}
vis[node] = true;
for (auto p : g[node]) {
if (p.first != par && cy(p.second.first, p.first, vis)) {
return cyc[node] ? false : (cyc[node] = true);
}
}
return false;
}
long long td(int node, int par = -1) {
std::vector <long long> ch;
for (auto p : g[node]) {
if (p.second.first == par || cyc[p.second.first]) {
continue;
}
ch.push_back(td(p.second.first, node) + p.second.second);
}
std::sort(ch.rbegin(), ch.rend());
if (ch.size()) {
cans[cc[node]] =
std::max(cans[cc[node]], (int) ch.size() > 1 ? ch[0] + ch[1] : ch.empty() ? 0LL : ch[0]);
}
return ch.size() ? ch[0] : 0LL;
}
std::vector <long long> sus;
void gse(int node, int par, std::vector <bool>& vis, std::vector <std::pair <long long, long long>>& seq) {
for (auto p : g[node]) {
if (p.second.first != par && cyc[p.second.first] && !vis[p.second.first]) {
vis[p.second.first] = true;
seq.emplace_back(sus[p.second.first], p.second.second);
gse(p.second.first, node, vis, seq);
}
}
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
std::cin >> n;
g.resize(n);
for (int i = 0; i < n; i++) {
int u, w; std::cin >> u >> w; u--;
g[u].push_back({ i, { i, w } });
g[i].push_back({ i, { u, w } });
}
std::vector <bool> vis(n, false);
cc.resize(n, -1);
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
c.resize(c.size() + 1);
cans.resize(cans.size() + 1, 0);
fc(i, vis);
for (int x : c.back()) {
cc[x] = (int) c.size() - 1;
}
}
cyc.resize(n, false);
vis = std::vector <bool> (n, false);
for (auto& v : c) {
cy(v[0], -1, vis);
}
sus.resize(n, 0);
for (int i = 0; i < n; i++) {
if (cyc[i]) {
sus[i] = td(i);
}
}
vis = std::vector <bool> (n, false);
for (int i = 0; i < n; i++) {
if (!vis[i] && cyc[i]) {
std::vector <std::pair <long long, long long>> seq;
gse(i, -1, vis, seq);
if ((int) seq.size() < 2) {
seq.clear();
for (int x : c[cc[i]]) {
if (cyc[x]) {
for (auto p : g[x]) {
if (cyc[p.second.first]) {
seq.emplace_back(sus[p.second.first], p.second.second);
}
}
}
}
std::sort(seq.begin(), seq.end(), [] (
std::pair <long long, long long> u, std::pair <long long, long long> v) {
return u.second < v.second;
});
seq = { seq.front(), seq.back() };
}
int m = seq.size();
Seg seg(m);
long long sum = 0;
for (int j = 0; j < m; j++) {
seg.update(j, j + 1, seq[j].first + (sum += seq[j].second));
}
for (int j = 0; j < m; j++) {
seg.update(0, m, -seq[j].second);
seg.update(j, j + 1, -seg.query(j, j + 1));
if (j) {
seg.update(j - 1, j, -seg.query(j - 1, j));
seg.update(j - 1, j, sum + seq[j - 1].first - seq[j].second);
}
cans[cc[i]] = std::max(cans[cc[i]], seq[j].first + seg.query(0, m));
}
}
}
long long ans = 0;
for (long long x : cans) {
ans += x;
}
std::cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
352 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Correct |
6 ms |
972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
2044 KB |
Output is correct |
| 2 |
Correct |
48 ms |
5872 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2388 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
8472 KB |
Output is correct |
| 2 |
Correct |
150 ms |
12508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
20820 KB |
Output is correct |
| 2 |
Correct |
436 ms |
34812 KB |
Output is correct |
| 3 |
Correct |
501 ms |
51316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
481 ms |
34916 KB |
Output is correct |
| 2 |
Correct |
686 ms |
77876 KB |
Output is correct |
| 3 |
Correct |
1504 ms |
89340 KB |
Output is correct |
| 4 |
Correct |
1311 ms |
121560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
372 ms |
100708 KB |
Output is correct |
| 2 |
Runtime error |
730 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
350 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
