oj.uz

Submission #1112938

# Submission time Handle Problem Language Result Execution time Memory
1112938 2024-11-15T09:43:50 Z akzytr Race (IOI11_race) C++17
0 / 100
 3000 ms 18512 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;
set<int> adj[MAXN];
map<ar<int, 2>, int> w;

int K;
int ANS = 1e9;

int sub[MAXN];
int 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) {
			return find_centroid(i, p, n);
		}
	}
	return x;
}

void dfs(int x, int p, map<int, int> &vis, map<int, int> &mi_edge, int we, int num_edge, bool upd) {
	if(upd) {
		if(vis[we]) {
			mi_edge[we] = min(mi_edge[we], num_edge);
		} else {
			vis[we] = 1;
			mi_edge[we] = num_edge;
		}
	} else {
		if(vis[K - we]) {
			ANS = min(ANS, num_edge + mi_edge[K - we]);
		}
	}

	for(int i : adj[x]) {
		if(i != p && we + w[{i, x}] <= K && !processed[i]) {
			dfs(i, x, vis, mi_edge, we + w[{i, x}], num_edge + 1, upd);
		}
	}
}
void process_centroid(int x) {
	map<int, int> vis;
	map<int, int> mi_edge;
	mi_edge[0] = 0;
	vis[0] = 1;

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

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);
		decompo(i);
	}
}

int best_path(int N, int Ked, int H[][2], int L[]) {
	fill(processed, processed + MAXN, 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 Execution timed out 3061 ms 18512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 18512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 18512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 18512 KB Time limit exceeded
2 Halted 0 ms 0 KB -