Submission #132974

#	Time	Username	Problem	Language	Result	Execution time	Memory
132974		wilwxk	Race (IOI11_race)	C++14	9 / 100	416 ms	19044 KiB

race

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

const int MAXN=2e5+5;
const int MAXX=1e6+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));
		fill(best, best+n+2, MAXN);
		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);

		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, 0);
			adv_scan(viz, cur, 1, peso, 1);
		}
		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, -1);
		}

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

private:
	int tam[MAXN], prof[MAXN];
	int best[MAXX];
	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 adv_scan(int cur, int p, int d, ll dd, int k) {
		if(dd>x) return;
		if(k==0) resp=min(resp, d+best[x-dd]);
		else if(k==1) best[dd]=min(best[dd], d);
		else best[dd]=MAXN;
		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, k);
		}
	}
	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:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
race.cpp:33: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:60: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: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57