Submission #387941

#	Time	Username	Problem	Language	Result	Execution time	Memory
387941		ritul_kr_singh	Race (IOI11_race)	C++17	100 / 100	631 ms	37264 KiB

race

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
#define v e.first
#define w e.second
#include "race.h"

const int MAXN = 2e5, INF = 1e9;

int ans = INF, k;

vector<vector<pair<int, int>>> g(MAXN);
vector<int> s(MAXN), len(1000001, INF);
vector<bool> r(MAXN);
vector<int> toUpdate;

int calcSize(int u, int p){
	s[u] = 1;
	for(auto &e : g[u]) if(v != p and !r[v]) s[u] += calcSize(v, u);
	return s[u];
}

void calcDist(int u, int p, int currLength, int currDist, int root){
	if(currDist>k) return;
	if(len[currDist]==INF) toUpdate.push_back(currDist);
	len[currDist] = min(len[currDist], currLength);

	for(auto &e : g[u]) if(v != p and !r[v]) calcDist(v, u, currLength+1, currDist+w, root);
}

void dfs(int u, int p, int currLength, int currDist, int root){
	if(currDist>k) return;
	ans = min(ans, len[k-currDist] + currLength);

	for(auto &e : g[u]) if(v != p and !r[v]) dfs(v, u, currLength+1, currDist+w, root);
}

int find(int u, int p, int treeSize){
	for(auto &e : g[u]) if(v != p and !r[v] and s[v] > treeSize/2) return find(v, u, treeSize);
	return u;
}

void decompose(int u){
	int c = find(u, u, calcSize(u, u));
	r[c] = true;
	for(auto &e : g[c]){
		if(r[v]) continue;
		dfs(v, c, 1, w, c);
		calcDist(v, c, 1, w, c);
	}
	ans = min(ans, len[k]);
	while(!toUpdate.empty()) len[toUpdate.back()] = INF, toUpdate.pop_back();
	for(auto &e : g[c]) if(!r[v]) decompose(v);
}


int best_path(int N, int K, int H[][2], int L[]){
	k = K;
	for(int i=0; i<N-1; ++i){
		g[H[i][0]].emplace_back(H[i][1], L[i]);
		g[H[i][1]].emplace_back(H[i][0], L[i]);
	}
	decompose(0);
	if(ans>N) ans = -1;
	return ans;
}

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