oj.uz

Submission #1113016

# Submission time Handle Problem Language Result Execution time Memory
1113016 2024-11-15T12:02:53 Z akzytr Race (IOI11_race) C++17
0 / 100
 15 ms 34496 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 = 2e6 + 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];
bool processed[MAXN];

void find_size(int x, int p) {
	sub[x] = 1;
	for(int i : adj[x]) {
		if(i != p && !processed[i]) {
			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 && !processed[i]) {
			return find_centroid(i, x, n);
		}
	}
	return x;
}

void dfs(int x, int p, int we, int num_edge, bool upd) {
	if(we > K) {
		return;
	}
	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 && !processed[i]) {
			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]) {
		if(processed[i]) {
			continue;
		}
		dfs(i, x, w[{i, x}], 1, false);
		dfs(i, x, w[{i, x}], 1, true);
	}
}

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

	processed[x] = 1;
	for(int i : adj[centroid]) {
		adj[i].erase(centroid);
		decompo(i, x);
	}
}

int best_path(int N, int Ked, int H[][2], int L[]) {
	fill(A, A + MAXK, 0);
	fill(BOOK_K, BOOK_K + MAXK, 0);
	fill(processed, processed + MAXN, false);
	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, -1);
	if(ANS != 1e9) {
		return ANS;
	}
	return -1;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34384 KB Output is correct
2 Correct 10 ms 34312 KB Output is correct
3 Correct 14 ms 34384 KB Output is correct
4 Correct 13 ms 34416 KB Output is correct
5 Correct 12 ms 34384 KB Output is correct
6 Correct 15 ms 34384 KB Output is correct
7 Correct 15 ms 34384 KB Output is correct
8 Correct 15 ms 34404 KB Output is correct
9 Correct 15 ms 34384 KB Output is correct
10 Incorrect 15 ms 34496 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34384 KB Output is correct
2 Correct 10 ms 34312 KB Output is correct
3 Correct 14 ms 34384 KB Output is correct
4 Correct 13 ms 34416 KB Output is correct
5 Correct 12 ms 34384 KB Output is correct
6 Correct 15 ms 34384 KB Output is correct
7 Correct 15 ms 34384 KB Output is correct
8 Correct 15 ms 34404 KB Output is correct
9 Correct 15 ms 34384 KB Output is correct
10 Incorrect 15 ms 34496 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34384 KB Output is correct
2 Correct 10 ms 34312 KB Output is correct
3 Correct 14 ms 34384 KB Output is correct
4 Correct 13 ms 34416 KB Output is correct
5 Correct 12 ms 34384 KB Output is correct
6 Correct 15 ms 34384 KB Output is correct
7 Correct 15 ms 34384 KB Output is correct
8 Correct 15 ms 34404 KB Output is correct
9 Correct 15 ms 34384 KB Output is correct
10 Incorrect 15 ms 34496 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34384 KB Output is correct
2 Correct 10 ms 34312 KB Output is correct
3 Correct 14 ms 34384 KB Output is correct
4 Correct 13 ms 34416 KB Output is correct
5 Correct 12 ms 34384 KB Output is correct
6 Correct 15 ms 34384 KB Output is correct
7 Correct 15 ms 34384 KB Output is correct
8 Correct 15 ms 34404 KB Output is correct
9 Correct 15 ms 34384 KB Output is correct
10 Incorrect 15 ms 34496 KB Output isn't correct
11 Halted 0 ms 0 KB -