| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 432559 |
2021-06-18T11:04:03 Z |
tengiz05 |
Islands (IOI08_islands) |
C++17 |
|
2000 ms |
131076 KB |
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::set<std::pair<int, int>>> e(n), al(n);
for (int i = 0; i < n; i++) {
int to, cost;
std::cin >> to >> cost;
to--;
e[i].emplace(to, cost);
e[to].emplace(i, cost);
al[i].emplace(to, cost);
al[to].emplace(i, cost);
}
std::vector<bool> vis(n);
int timer = 0;
std::vector<int> in(n), low(n);
std::vector<std::tuple<int, int, int>> br;
std::function<void(int, int)> dfs = [&](int u, int p) {
in[u] = low[u] = timer++;
vis[u] = true;
for (auto [v, w] : e[u]) {
if (v == p) {
continue;
}
if (vis[v]) {
low[u] = std::min(low[u], in[v]);
} else {
dfs(v, u);
low[u] = std::min(low[u], low[v]);
if (low[v] > low[u]) {
// bridge u -> v
br.emplace_back(u, v, w);
}
}
}
};
for (int i = 0; i < n; i++) {
if (!vis[i])
dfs(0, -1);
}
for (auto [x, y, z] : br) {
al[x].erase(al[x].lower_bound({y, z}));
al[y].erase(al[y].lower_bound({x, z}));
}
std::vector<i64> v{0}, pos(n, 0), comp(n), sum(n);
std::iota(pos.begin(), pos.end(), 0);
std::vector<std::vector<int>> contain;
vis.assign(n, false); timer = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
comp[i] = timer;
pos[i] = v.size();
v.push_back(v.back());
contain.push_back({});
if (al[i].size()) {
int u = i;
contain[timer].push_back(u);
vis[u] = true;
while (!vis[al[u].begin()->first] || !vis[(++al[u].begin())->first]) {
i64 cost;
if (vis[al[u].begin()->first]) {
u = (++al[u].begin())->first;
cost = (++al[u].begin())->second;
} else {
u = al[u].begin()->first;
cost = al[u].begin()->second;
}
contain[timer].push_back(u);
vis[u] = true;
comp[u] = timer;
pos[u] = v.size();
sum[timer] += cost;
v.push_back(v.back() + cost);
}
if (vis[al[u].begin()->first]) {
sum[timer] += (++al[u].begin())->second;
} else {
sum[timer] += al[u].begin()->second;
}
}
timer++;
}
// std::cerr << "what the fuck\n";
// for (int i = 0; i < n; i++) {
// std::cout << comp[i] << " \n"[i == n - 1];
// }
for (int i = 0; i < n; i++) {
e[i].clear();
}
for (auto [x, y, z] : br) {
e[x].insert({y, z});
e[y].insert({x, z});
}
i64 ans = 0;
std::vector<i64> f(n);
for (int i = 0; i < timer; i++) {
i64 res = 0;
std::function<i64(int, int)> dfs2 = [&](int u, int p) -> i64 {
i64 mx = 0;
for (auto [v, w] : e[u]) {
if (v != p) {
mx = std::max(mx, dfs2(v, u) + w);
}
}
return mx;
};
for (auto u : contain[i]) {
f[u] = dfs2(u, -1);
}
for (auto U : contain[i]) {
for (auto V : contain[i]) {
if (U == V) continue;
assert(comp[U] == comp[V]);
if (pos[U] > pos[V]) std::swap(U, V);
if (U == 1 && V == 6) {
// std::cout << "YES ";
// std::cout << sum[comp[U]] << " " << v[pos[V]] - v[pos[U] - 1] << "\n";
}
res = std::max(res, f[U] + f[V] + std::max(v[pos[V]] - v[pos[U] - 1], sum[comp[U]] - (v[pos[V]] - v[pos[U] - 1])));
}
}
ans += res;
// std::cout << ans << "\n";
}
std::cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
476 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
316 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
252 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 10 |
Execution timed out |
2086 ms |
332 KB |
Time limit exceeded |
| 11 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
5332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2029 ms |
21656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2064 ms |
81592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
131072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
228 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
156 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
