| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1018639 |
2024-07-10T07:45:32 Z |
Muaath_5 |
Islands (IOI08_islands) |
C++17 |
|
478 ms |
131072 KB |
#pragma GCC optimize("Og")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 1e6+5;
// input
int n;
vector<pair<int, int>> adj[N]; // 8M
map<pii, int> edge; // count duplicate // 12M
map<pii, int> we; // weight of edge // 12M
// dfs
vector<bool> vis(N); // 1M or less
vector<int> stck; // 1M
vector<int> cyc; // 1M
// diameter dfs
pii remedge;
int blk[2];
int mx[N]; // 1M
ll a[N]; // 8M
//ll pref[N]; // 8M
//ll mxdep[N]; // 8M
void dfs(int node, int par=0) {
vis[node] = 1;
stck.push_back(node);
for (auto &[ch, cost] : adj[node]) {
if (!vis[ch])
dfs(ch, node);
else if (!cyc.size() && edge[{node, ch}] == 2) {
cyc.push_back(node);
cyc.push_back(ch);
}
else if (!cyc.size() && vis[ch] && ch != par) {
bool st = 0;
for (int cur : stck) {
if (cur == ch) st = 1;
if (st) cyc.push_back(cur);
}
}
}
stck.pop_back();
}
ll farthest_dp(int node, int par=0) {
mx[node] = node;
ll mxdep = 0;
for (auto [ch, cost] : adj[node]) {
if (blk[0] == ch || blk[1] == ch || ch == par) continue;
if (make_pair(node, ch) != remedge && make_pair(ch, node) != remedge) {
ll mxdepch = farthest_dp(ch, node);
if (mxdepch + cost > mxdep) {
mxdep = mxdepch + cost;
mx[node] = mx[ch];
}
}
}
return mxdep;
}
ll solve_for(int node)
{
cyc.clear();
dfs(node);
const ll L = cyc.size();
//assert(L > 1);
// cerr << "#" << node << ": ";
// cerr << L << ": ";
// for(int i:cyc)cerr<<i<<' ';
// cerr<<"| ";
// remove an edge from the cycle and find diameter
if (L > 2)
remedge = {cyc[0], cyc[1]};
else
remedge = {-1, -1};
farthest_dp(node);
int fr = mx[node];
ll diam = farthest_dp(fr);
// a[i] = max depth of tree going from i not in cycle direction
// prefix sums
for (int i = 0; i < L; i++) {
blk[0] = cyc[(i+1)%L];
blk[1] = cyc[(i-1+L)%L];
a[i] = farthest_dp(cyc[i]);
}
// for (int i = 0; i < L; i++)
// cerr << a[i] << ' ';
// cerr << "| ";
// cost of path(i,j) = a[i] + a[j] + (p[i] - p[j]);
// maintain maximum a[j] - p[j], and the answer for suffix i:
//
ll prvmx = 0, prvmx2 = 0;;
ll sol = 0;
ll pref = 0;
for (int i = 1; i < L; i++)
pref += we[{cyc[i], cyc[i-1]}];
const ll LL = pref + we[{cyc[L-1], cyc[0]}];
if (L == 2) {
sol = *max_element(a, a+L) + we[{cyc[0], cyc[1]}];
goto RET;
}
pref = 0;
prvmx = prvmx2 = a[0];
for (int i = 1; i < L; i++) {
pref += we[{cyc[i], cyc[i-1]}];
sol = max(sol, a[i] + pref + prvmx);
sol = max(sol, LL + a[i] - pref + prvmx2);
prvmx2 = max(prvmx2, a[i] + pref);
prvmx = max(prvmx, a[i] - pref);
}
RET:
return max(diam, sol);
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// stck.reserve(N/2);
// cyc.reserve(N/2);
cin >> n;
for (int i = 1; i <= n; i++) {
int u, w;
cin >> u >> w;
adj[i].push_back({u, w});
adj[u].push_back({i, w});
edge[{i,u}]++, edge[{u,i}]++;
we[{i, u}] = we[{u, i}] = max(we[{i, u}], w);
}
ll sum = 0;
for (int i = 1; i <= n; i++)
if (!vis[i])
sum += solve_for(i);
cout << sum;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
7 ms |
27428 KB |
Output is correct |
| 3 |
Correct |
10 ms |
27608 KB |
Output is correct |
| 4 |
Correct |
7 ms |
27320 KB |
Output is correct |
| 5 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 6 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 7 |
Correct |
7 ms |
27448 KB |
Output is correct |
| 8 |
Correct |
8 ms |
27228 KB |
Output is correct |
| 9 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 10 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 11 |
Correct |
7 ms |
27228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
27736 KB |
Output is correct |
| 2 |
Correct |
9 ms |
27688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
27992 KB |
Output is correct |
| 2 |
Correct |
14 ms |
28764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
32092 KB |
Output is correct |
| 2 |
Correct |
64 ms |
39964 KB |
Output is correct |
| 3 |
Correct |
34 ms |
33744 KB |
Output is correct |
| 4 |
Correct |
19 ms |
30300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
45396 KB |
Output is correct |
| 2 |
Correct |
103 ms |
59756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
265 ms |
92244 KB |
Output is correct |
| 2 |
Correct |
320 ms |
108824 KB |
Output is correct |
| 3 |
Correct |
389 ms |
127404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
273 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
478 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
395 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
