Submission #1261993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261993		hiepsimauhong	Race (IOI11_race)	C++20	100 / 100	810 ms	32712 KiB

race

#include <bits/stdc++.h>
using namespace std;

#ifndef KURUMI
#include "race.h"
#endif

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x " = " << (x) << "]"
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}
template<typename T> T rnd(T a, T b) {
    return uniform_int_distribution<T>(a, b)(rng);
}

typedef long long                  ll;
typedef long double                ld;
typedef pair<int, int>             pii;
typedef pair<long long, int>       pli;
typedef pair<long long, long long> pll;
 
const int N = 2e5 + 3;

int n, k;
vector<pii> adj[N];

int answer = INT_MAX;
int siz[N];
bool isCentroid[N];
map<int, int> lens;

void dfsSize(int u, int p) {
	siz[u] = 1;
	for(pii it : adj[u]) {
		int v, w; tie(v, w) = it;
		if(v != p && !isCentroid[v]) {
			dfsSize(v, u);
			siz[u] += siz[v];
		}
	}
}

int findCentroid(int u, int p, int treeSize) {
	for(pii it : adj[u]) {
		int v = it.fi;
		if(v != p && !isCentroid[v] && siz[v] > treeSize / 2) {
			return findCentroid(v, u, treeSize);
		}
	}
	return u;
}

void update(int u, int p, int wgt, int len) {
	if(lens.count(k - wgt)) 
		minimize(answer, len + lens[k - wgt]);

	for(pii it : adj[u]) {
		int v, w; tie(v, w) = it;
		if(!isCentroid[v] && v != p) {
			update(v, u, wgt + w, len + 1);
		}
	}
}

void add(int u, int p, int wgt, int len) {
	if(wgt <= k) {
		if(lens.count(wgt)) minimize(lens[wgt], len);
		else lens[wgt] = len;
	}

	for(pii it : adj[u]) {
		int v, w; tie(v, w) = it;
		if(!isCentroid[v] && v != p) {
			add(v, u, wgt + w, len + 1);
		}
	}
}

void decompose(int u) {
	dfsSize(u, -1);
	u = findCentroid(u, -1, siz[u]);

	lens.clear(); lens[0] = 0;
	for(pii it : adj[u]) {
		int v, w; tie(v, w) = it;
		if(!isCentroid[v]) {
			update(v, u, w, 1);
			add(v, u, w, 1);
		}
	}

	isCentroid[u] = true;
	for(pii it : adj[u]) {
		int v = it.fi;
		if(!isCentroid[v]) decompose(v);
	}
}

int process() {
	dfsSize(1, -1);
	decompose(1);
	return (answer == INT_MAX ? -1 : answer);
}

int best_path(int _n, int _k, int _h[][2], int _l[]) {
 	n = _n; k = _k;
 	for(int i = 0; i < n - 1; i++) {
 		int u = _h[i][0], v = _h[i][1], w = _l[i];
 		adj[u].emplace_back(v, w);
 		adj[v].emplace_back(u, w);
 	}

 	return process();
}

#ifdef KURUMI
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    int H[2610][2];
    int L[1006];

    cin >> n >> k;
    for(int i = 0; i < n - 1; i++) 
    	cin >> H[i][0] >> H[i][1];
    for(int i = 0; i < n - 1; i++)
    	cin >> L[i];

   	cout << best_path(n, k, H, L) << endl;

    return 0;
}
#endif

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57