oj.uz

Submission #878195

# Submission time Handle Problem Language Result Execution time Memory
878195 2023-11-24T07:04:34 Z SanguineChameleon Closing Time (IOI23_closing) C++17
8 / 100
 123 ms 38968 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

namespace cardboard {
	int solve(int N, long long K, vector<pair<long long, long long>> boxes) {
		return 0;
	}
}

namespace tree {
	vector<vector<pair<int, int>>> adj;

	void init(int N) {
		adj.resize(N);
		for (int i = 0; i < N; i++) {
			adj[i].clear();
		}
	}

	void add_edge(int u, int v, int w) {
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}

	void dfs(int u, int p, vector<long long> &dist) {
		for (auto [v, w]: adj[u]) {
			if (v != p) {
				dist[v] = dist[u] + w;
				dfs(v, u, dist);
			}
		}
	}
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
	tree::init(N);
	for (int i = 0; i < N - 1; i++) {
		tree::add_edge(U[i], V[i], W[i]);
	}
	vector<long long> distX(N), distY(N);
	tree::dfs(X, -1, distX);
	tree::dfs(Y, -1, distY);
	vector<long long> dists(distX.begin(), distX.end());
	dists.insert(dists.end(), distY.begin(), distY.end());
	sort(dists.begin(), dists.end());
	int res = 0;
	long long sum = 0;
	for (auto d: dists) {
		if (sum + d <= K) {
			sum += d;
			res++;
		}
		else {
			break;
		}
	}
	int cnt = 0;
	vector<pair<long long, long long>> boxes(N);
	for (int i = 0; i < N; i++) {
		if (distX[i] + distY[i] == distX[Y]) {
			cnt++;
			K -= min(distX[i], distY[i]);
			boxes[i] = {max(distX[i], distY[i]), K + 1};
		}
		else {
			boxes[i] = {min(distX[i], distY[i]), max(distX[i], distY[i])};
		}
	}
	if (K >= 0) {
		res = max(res, cnt + cardboard::solve(N, K, boxes));
	}
	return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 34272 KB Output is correct
2 Correct 123 ms 38968 KB Output is correct
3 Correct 64 ms 5388 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -