oj.uz

Submission #840999

# Submission time Handle Problem Language Result Execution time Memory
840999 2023-09-01T03:54:29 Z jhwest2 Closing Time (IOI23_closing) C++17
8 / 100
 111 ms 26196 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 202020;

long long dx[MAXN], dy[MAXN];
vector<pair<int, int>> g[MAXN];

void dfs_x(int p, int v) {
	for (auto [w, x] : g[v]) if (p != x) {
		dx[x] = dx[v] + w;
		dfs_x(v, x);
	}
}
void dfs_y(int p, int v) {
	for (auto [w, x] : g[v]) if (p != x) {
		dy[x] = dy[v] + w;
		dfs_y(v, x);
	}
}
bool dead[MAXN];
int max_score(int N, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W)
{
	for (int i = 0; i < N - 1; i++) {
		g[U[i]].push_back({W[i], V[i]});
		g[V[i]].push_back({W[i], U[i]});
	}
	dx[X] = 0;
	dy[Y] = 0;
	dfs_x(-1, X);
	dfs_y(-1, Y);
	long long D = dx[Y];
	long long vx = X;
	long long vy = Y;
	long long tx = 0;
	long long ty = 0;
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			if (dx[i] <= dy[i] && tx < dx[i]) {
				vx = i;
				tx = dx[i];
			}
			if (dx[i] > dy[i] && ty < dy[i]) {
				vy = i;
				ty = dy[i];
			}
		}
	}
	// no overlap
	priority_queue<tuple<long long, int, int, int>> pq;
	pq.push({0, X, -1, 0});
	pq.push({0, Y, -1, 1});
	int ans1 = 0;
	long long tk = K;
	while (!pq.empty()) {
		auto [c, v, p, t] = pq.top();
		pq.pop();
		c = -c;
		if (c > K) break;
		// cout << ((t == 0) ? "X" : "Y") << ' ' << c << ' ' << "vertex " << v << "??\n";
		K -= c;
		++ans1;
		for (auto [w, x] : g[v]) if (p != x) {
			if ((v == vx && x == vy) || (v == vy && x == vx)) continue;
			if (t == 0)
				pq.push({-dx[x], x, v, 0});
			else
				pq.push({-dy[x], x, v, 1});
		}
	}
	// yes overlap
	K = tk;
	int ans2 = 0;
	while (!pq.empty()) pq.pop();
	long long t = 0;
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			t += min(dx[i], dy[i]);
			++ans2;
			dead[i] = true;
		}
	}
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			for (auto [w, x] : g[i]) if (!dead[x]) {
				if (dx[x] <= dy[x]) {
					pq.push({-dx[x], x, i, 0});
				}
				else {
					pq.push({-dy[x], x, i, 1});
				}
			}
		}
	}
	pq.push({dy[vy] - dx[vy], vy, vx, 0});
	pq.push({dx[vx] - dy[vx], vx, vy, 1});
	if (t <= K) {
		K -= t;
		// cout << "we have " << K << '\n';
		while (!pq.empty()) {
			auto [c, v, p, t] = pq.top();
			pq.pop();
			c = -c;
			// if (t != 2) {
			// 	cout << ((t == 0) ? "X" : "Y") << ' ' << "cost " << c << ' ' << "vertex " << v << '\n';
			// 	if (dead[v]) cout << "Progess\n";
			// 	else cout << "New\n";
			// }
			// else {
			// 	cout << "Upgrade " << v << "with cost " << c << '\n';
			// }
			if (c > K) break;
			
			K -= c;
			++ans2;
			if (t == 2) continue;
			if (!dead[v]) {
				if (t == 0) pq.push({dx[v] - dy[v], v, p, 2});
				else pq.push({dy[v] - dx[v], v, p, 2});
				for (auto [w, x] : g[v]) if (p != x) {
					if (t == 0) pq.push({-dx[x], x, v, 0});
					else pq.push({-dy[x], x, v, 1});
				}
			}
			else {
				for (auto [w, x] : g[v]) if (p != x) {
					if (!dead[x]) {
						if (t == 0) pq.push({-dx[x], x, v, 0});
						else pq.push({-dy[x], x, v, 0});
					}
					else {
						if (t == 0) pq.push({-dx[v] + dy[v], x, v, 0});
						else pq.push({-dy[v] + dx[v], x, v, 1});
					}
				}
			}
		}
		ans1 = max(ans1, ans2);
	}
	for (int i = 0; i < N; i++) g[i].clear(), dead[i] = false;
	return ans1;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 25764 KB Output is correct
2 Correct 107 ms 26196 KB Output is correct
3 Correct 55 ms 7584 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '30', found: '42'
4 Halted 0 ms 0 KB -