Submission #344817

#	Time	Username	Problem	Language	Result	Execution time	Memory
344817		Tosic	Race (IOI11_race)	C++14	21 / 100	1176 ms	262148 KiB

race

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

int n, k, ans, minSz, curCn, minDistance[10*maxn];
bool isC[maxn];
vector<vector<pair<int, int> > > gr;
vector<int> subSz;

int findCentroid(int x, int p, int dist, int price, int n){
	subSz[x] = 1;
	int tmpM = 0;
	for(auto pr : gr[x]){
		int i = pr.first,c = pr.second;
		if(isC[i] or i == p){
			continue;
		}
		subSz[x] += findCentroid(i, x, dist+1, price+c, n);
		tmpM = max(subSz[i], tmpM);
	}
	tmpM = max(tmpM, n-subSz[x]);
	if(minSz > tmpM){
		minSz = tmpM;
		curCn = x;
	}
	return subSz[x];
}

vector<int> chPrices;

void dfs(int x, int p, int dist, int price, bool isAdding){
	if(price>=maxn*10){
		return;
	}
	if(isAdding and price < maxn*10){
		minDistance[price] = min(minDistance[price],dist);
		chPrices.push_back(price);
	} else {
		if(k - price >= 0){
			ans = min(ans, dist + minDistance[k-price]);
		}
	}
	for(auto tmp:gr[x]){
		int i = tmp.first, j = tmp.second;
		if(isC[i] or i ==p){
			continue;
		}
		dfs(i, x, dist+1, price + j, isAdding);
	}
}

void findR(int x, int n){
	minSz = 1e9;
	curCn = x;
	findCentroid(x, -1, 0, 0, n);
	isC[curCn] = 1;
	for(auto tmp:gr[curCn]){
		int i = tmp.first, j = tmp.second;
		if(!isC[i]){
			dfs(i, curCn, 1, j, 0);
			dfs(i, curCn, 1, j, 1);
		}

	}
	//unique(chPrices.begin(), chPrices.end());
	for(auto x : chPrices){
		minDistance[x] = 1e9;
	}
	minDistance[0] = 0;
	chPrices.clear();
	for(auto tmp:gr[curCn]){
		int i = tmp.first, j = tmp.second;
		if(!isC[i]){
			findR(i, subSz[i]);
		}
	}
}

int best_path(int n, int k1, int h[][2], int l[]){
	k = k1;
	gr.resize(n, vector<pair<int, int> >());
	for(int i = 0; i < n-1; ++i){
		int x, y, w;
		x = h[i][0];
		y = h[i][1];
		w = l[i];
		gr[x].push_back({y, w});
		gr[y].push_back({x, w});
	}
	subSz.resize(n, 0);
	for(int i = 1; i < maxn*10; ++i){
		minDistance[i] = 1e9;
	}
	ans = 1e9;
	findR(0, n);
	if(ans != 1e9){
		return ans;
	} else {
		return -1;
	}
}

Compilation message (stderr)

race.cpp: In function 'void findR(int, int)':
race.cpp:72:22: warning: unused variable 'j' [-Wunused-variable]
   72 |   int i = tmp.first, j = tmp.second;
      |                      ^

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