oj.uz

Submission #1012877

# Submission time Handle Problem Language Result Execution time Memory
1012877 2024-07-02T19:24:32 Z Muaath_5 Islands (IOI08_islands) C++17
70 / 100
 384 ms 131072 KB 
#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;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 11 ms 24156 KB Output is correct
4 Correct 10 ms 24080 KB Output is correct
5 Correct 14 ms 23900 KB Output is correct
6 Correct 10 ms 23948 KB Output is correct
7 Correct 15 ms 23912 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 24152 KB Output is correct
10 Correct 10 ms 23964 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24408 KB Output is correct
2 Correct 12 ms 24116 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24412 KB Output is correct
2 Correct 14 ms 25436 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28764 KB Output is correct
2 Correct 62 ms 36904 KB Output is correct
3 Correct 50 ms 30508 KB Output is correct
4 Correct 21 ms 27224 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 42256 KB Output is correct
2 Correct 94 ms 56836 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 87620 KB Output is correct
2 Correct 319 ms 102736 KB Output is correct
3 Correct 340 ms 121824 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 384 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 331 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -