Submission #132963

#	Time	Username	Problem	Language	Result	Execution time	Memory
132963		wilwxk	Race (IOI11_race)	C++14	21 / 100	3086 ms	30472 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e5+5;
vector<int> g[MAXN], pes[MAXN];
int n, respf;
ll x;

class solution {
public:
	int resp=MAXN;
	void init() {
		tam[n]=0;
		memset(prof, 0, sizeof(prof));
		solve(0, 1);
	}
	void solve(int cur, int k) {
		basic_scan(cur, cur);
		cur=find_centroid(cur, cur, tam[cur]);
		prof[cur]=k;
		
		// printf(">> %d <<\n", cur);

		best.clear(); best[0]={0, 0, n};
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; ll peso=pes[cur][i];
			adv_scan(viz, cur, 1, peso, viz);
		}
		for(auto cur : best) {
			ll d=cur.first;
			if(best.find(x-d)==best.end()) continue;
			int a=get<2>(cur.second);
			int val=get<0>(cur.second);

			auto outro=best[x-d];
			int b=get<2>(outro);
			int val2= b==a ? get<1>(outro) : get<0>(outro);

			// printf("d= %lld : %d %d >> %lld + %lld -1\n", d, a, b, val, val2);
			resp=min(resp, val+val2);
		}

		for(auto viz : g[cur]) {
			if(prof[viz]) continue;
			solve(viz, k+1);
		}
	}

private:
	int tam[MAXN], prof[MAXN];
	map<ll, tuple<int, int, int> > best;
	void basic_scan(int cur, int p) {
		tam[cur]=1;
		for(auto viz : g[cur]) {
			if(viz==p||prof[viz]) continue;
			basic_scan(viz, cur);
			tam[cur]+=tam[viz];
		}
	}
	void melhora(int cur, ll dd, int d) {
		if(best.find(dd)==best.end()) {
			best[dd]={d, MAXN, cur};
			return;
		}
		int a, b, c; tie(a, b, c)=best[dd];
		if(cur==c) best[dd]={min(a, d), b, c};
		else if(d<b) best[dd]={a, d, c};
	}
	void adv_scan(int cur, int p, int d, ll dd, int raiz) {
		melhora(raiz, dd, d);
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; ll peso=pes[cur][i];
			if(viz==p||prof[viz]) continue;
			adv_scan(viz, cur, d+1, dd+peso, raiz);
		}
	}
	int find_centroid(int cur, int p, int val) {
		int grande=n;
		for(auto viz : g[cur]) if(viz!=p&&!prof[viz]&&tam[viz]>tam[grande]) grande=viz;
		if(tam[grande]*2<=val) return cur;
		return find_centroid(grande, cur, val);
	}

};

int best_path(int N, int K, int H[][2], int L[])
{
	n=N; x=K;
	for(int i=0; i<n-1; i++) {
		int a=H[i][0]; int b=H[i][1];
		g[a].push_back(b); pes[a].push_back(L[i]);
		g[b].push_back(a); pes[b].push_back(L[i]);
	}

	solution sol;
	sol.init();

	respf=sol.resp;
	if(respf>n) respf=-1;

	return respf;
}

Compilation message (stderr)

race.cpp: In member function 'void solution::solve(int, int)':
race.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
race.cpp: In member function 'void solution::adv_scan(int, int, int, ll, int)':
race.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~

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