Submission #387928

#	Time	Username	Problem	Language	Result	Execution time	Memory
387928		ritul_kr_singh	Race (IOI11_race)	C++17	0 / 100	10 ms	15564 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;

int ans = 1e9, k;

vector<vector<pair<int, int>>> g(MAXN);
vector<int> s(MAXN);
vector<bool> r(MAXN);

vector<map<int, int>> d(MAXN);

int calcSize(int u, int p){
	s[u] = 0;
	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){
	int &x = d[root][currDist];
	if(!x) x = currLength+1;
	else x = min(x, currLength+1);

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

void dfs(int u, int p, int currLength, int currDist, int root){
	if(d[root][k-currDist]) ans = min(ans, d[root][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[u] = 1;
	for(auto &e : g[c]){
		if(r[v]) continue;
		dfs(v, c, 1, w, c);
		calcDist(v, c, 1, w, c);
	}
	if(d[c][k]) ans = min(ans, d[c][k]);
	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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57