| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 432567 |
2021-06-18T11:11:57 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] > in[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";
}
// for (int i = 0; i < n; i++) {
// std::cout << f[i] << " \n"[i == n - 1];
// }
std::cout << ans << "\n";
return 0;
}
/*
auto dij = [&](int s) {
std::priority_queue<std::pair<int, int>> q;
q.emplace(0, s);
std::vector<int> dist(n, -1e9);
dist[s] = 0;
while (!q.empty()) {
auto [d, u] = q.top();
if (s == 0) {
std::cout << u << "\n";
}
q.pop();
for (auto [v, w] : e[u]) {
if (dist[v] < dist[u] + w) {
q.emplace(dist[v], v);
}
}
}
std::pair<int, int> mx = {0, s};
for (int i = 0; i < n; i++) {
mx = std::max(mx, {dist[i], i});
if (s == 0) {
std::cout << dist[i] << " ";
}
}
return mx;
};
int ans = 0;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0 || true) {
auto [dist, u] = dij(i);
ans = std::max(ans, dist);
}
}*/
| # |
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 |
460 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
204 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 |
2073 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 |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2083 ms |
5028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
20892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2082 ms |
79088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2019 ms |
130532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
235 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
158 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
