oj.uz

Submission #1012507

# Submission time Handle Problem Language Result Execution time Memory
1012507 2024-07-02T09:08:13 Z Muaath_5 Islands (IOI08_islands) C++17
9 / 100
 420 ms 131076 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 1e6+1;

int n;
vector<pair<int, ll>> adj[N];
map<pii, int> edge;
map<pii, ll> we;

bool vis[N], vis2[N];
vector<int> stck;
vector<int> cyc; 
int sz = 0;
void dfs(int node, int par=0) {
	sz++;
	vis[node] = 1;
	stck.push_back(node);
	for (auto [ch, cost] : adj[node]) {
		if (!cyc.size() && edge[{node, ch}] == 2) {
			cyc.push_back(node);
			cyc.push_back(ch);
		}
		if (vis[ch] && ch != par) {
			if (!cyc.size()) {
				bool st = 0;
				for (int cur : stck) {
					if (cur == ch) st = 1;
					if (st) cyc.push_back(cur);
				}
			}
		}
		else if (!vis[ch])
			dfs(ch, node);
	}
	stck.pop_back();
}

pii remedge;

int mx[N];
ll mxdep[N];
void farthest_dp(int node, int par=0) {
	mx[node] = node;
	mxdep[node] = 0;
	for (auto [ch, cost] : adj[node]) {
		if (vis2[ch] || ch == par) continue;
		if (make_pair(node, ch) != remedge && make_pair(ch, node) != remedge) {
			farthest_dp(ch, node);
			if (mxdep[ch] + cost > mxdep[node]) {
				mxdep[node] = mxdep[ch] + cost;
				mx[node] = mx[ch];
			}
		}
	}
}

ll solve_for(int node)
{
	if (vis[node]) return 0;
	sz = 0;
	cyc.clear();
	dfs(node);
	const ll L = cyc.size();

	// 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];
	farthest_dp(fr);
	ll diam = mxdep[fr];
	
	
	// a[i] = max depth of tree going from i not in cycle direction 
	// prefix sums
	ll a[L] = {};
	memset(vis2, 0, sizeof vis2);
	for (int i = 0; i < L; i++) {
		vis2[cyc[(i+1)%L]] = 1;
		vis2[cyc[(i-1+L)%L]] = 1;
		farthest_dp(cyc[i]);
		a[i] = mxdep[cyc[i]];
		vis2[cyc[(i+1)%L]] = 0;
		vis2[cyc[(i-1+L)%L]] = 0;
	}
	
	// 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;
	ll sol = 0;
	ll pref[L] = {};
	if (L == 2) {
		sol = *max_element(a, a+L) + we[{cyc[0], cyc[1]}];
		goto RET;
	}
	
	
	pref[0] = 0;
	
	// for (int i = 0; i < L; i++)
		// cerr << a[i] << ' ';
	// cerr << "| ";
	
	for (int i = 1; i < L; i++) {
		pref[i] = pref[i-1] + we[{cyc[i], cyc[i-1]}];
		prvmx = max(prvmx, a[i] - pref[i]);
		sol = max(sol, a[i] + pref[i] + prvmx);
	}

	prvmx = 0;
	for (int i = 1; i < L; i++) {
		pref[i] = pref[i-1] + we[{cyc[i], cyc[i-1]}];
		prvmx = max(prvmx, a[i] - (L - pref[i]));
		sol = max(sol, a[i] + pref[i] + prvmx);
	}
	
	RET:
	return max(diam, sol);
}


int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int u;
		ll 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++) {
		ll x = solve_for(i);
		//if (x) cerr << x << '\n';
		sum += x;
	}
		
	cout << sum;
}

Subtask #1
9.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 25692 KB Output isn't correct
2 Incorrect 6 ms 25948 KB Output isn't correct
3 Incorrect 7 ms 25944 KB Output isn't correct
4 Correct 7 ms 25692 KB Output is correct
5 Incorrect 6 ms 25692 KB Output isn't correct
6 Incorrect 7 ms 25768 KB Output isn't correct
7 Incorrect 6 ms 25688 KB Output isn't correct
8 Incorrect 6 ms 25688 KB Output isn't correct
9 Incorrect 7 ms 25692 KB Output isn't correct
10 Correct 6 ms 25948 KB Output is correct
11 Correct 9 ms 25948 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 26200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 26456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 30812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 44628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 280 ms 91580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 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 420 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 332 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -