oj.uz

Submission #1113008

# Submission time Handle Problem Language Result Execution time Memory
1113008 2024-11-15T11:35:05 Z akzytr Race (IOI11_race) C++17
0 / 100
 39 ms 45648 KB 
#include "race.h"
#include <bits/stdc++.h>
#define ve vector
#define pb push_back
#define ar array
#define ll long long
using namespace std;

const int MAXN = 3e5;
const int MAXK = 1e6 + 1;
set<int> adj[MAXN];
map<ar<int, 2>, int> w;

int K;
int ANS = 1e9;

int BOOK = 1;

int sub[MAXN];
int A[MAXK];
int BOOK_K[MAXK];

void find_size(int x, int p) {
	sub[x] = 1;
	for(int i : adj[x]) {
		if(i != p) {
			find_size(i, x);
			sub[x] += sub[i];
		}
	}
}
int find_centroid(int x, int p, int n) {
	for(int i : adj[x]) {
		if(sub[i] > n / 2 && i != p) {
			return find_centroid(i, x, n);
		}
	}
	return x;
}

void dfs(int x, int p, int we, int num_edge, bool upd) {
	assert(we <= K);
	if(upd) {
		if(BOOK_K[we] != BOOK) {
			BOOK_K[we] = BOOK;
			A[we] = num_edge;
		} else {
			A[we] = min(A[we], num_edge);
		}
	} else {
		if(BOOK_K[K - we] == BOOK) {
			ANS = min(ANS, num_edge + A[K - we]);
		}
	}

	for(int i : adj[x]) {
		if(i != p && we + w[{i, x}] <= K) {
			dfs(i, x, we + w[{i, x}], num_edge + 1, upd);
		}
	}
}
void process_centroid(int x) {
	BOOK++;
	A[0] = 0;
	BOOK_K[0] = BOOK;

	for(int i : adj[x]) {
		dfs(i, x, w[{i, x}], 1, false);
		dfs(i, x, w[{i, x}], 1, true);
	}
}

void decompo(int x) {
	find_size(x, -1);
	int centroid = find_centroid(x, -1, sub[x]);
	process_centroid(centroid);

	for(int i : adj[centroid]) {
		adj[i].erase(centroid);
	}

	for(int i : adj[centroid]) {
		decompo(i);
	}
}

int best_path(int N, int Ked, int H[][2], int L[]) {
	fill(A, A + MAXK, 0);
	fill(BOOK_K, BOOK_K + MAXK, 0);
	for(int i = 0; i < N - 1; i++) {
		int a, b;
		a = H[i][0];
		b = H[i][1];

		adj[a].insert(b);
		adj[b].insert(a);
		w[{a, b}] = L[i];
		w[{b, a}] = L[i];
	}
	K = Ked;
	decompo(0);
	if(ANS != 1e9) {
		return ANS;
	}
	return -1;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26192 KB Output is correct
2 Correct 8 ms 26192 KB Output is correct
3 Correct 8 ms 24240 KB Output is correct
4 Correct 10 ms 22608 KB Output is correct
5 Runtime error 39 ms 45648 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26192 KB Output is correct
2 Correct 8 ms 26192 KB Output is correct
3 Correct 8 ms 24240 KB Output is correct
4 Correct 10 ms 22608 KB Output is correct
5 Runtime error 39 ms 45648 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26192 KB Output is correct
2 Correct 8 ms 26192 KB Output is correct
3 Correct 8 ms 24240 KB Output is correct
4 Correct 10 ms 22608 KB Output is correct
5 Runtime error 39 ms 45648 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26192 KB Output is correct
2 Correct 8 ms 26192 KB Output is correct
3 Correct 8 ms 24240 KB Output is correct
4 Correct 10 ms 22608 KB Output is correct
5 Runtime error 39 ms 45648 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -