Submission #349028

#	Time	Username	Problem	Language	Result	Execution time	Memory
349028		Mefarnis	Race (IOI11_race)	C++14	100 / 100	717 ms	38480 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
#define maxn 200000
#define maxk 1000001
#define pb push_back
using namespace std;
typedef pair<int,int> pi;

int n,k,ans;
int sz[maxn];
int dist[maxn];
int depth[maxn];
bool mark[maxn];
int minDepth[maxk];
vector<int> nodes;
vector<pi> adj[maxn];

int dfs(int u , int dad , int de , int di) {
	sz[u] = 1;
	dist[u] = di;
	depth[u] = de;
	nodes.pb(u);
	int deg = adj[u].size();
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i].fi;
		int vdi = di + adj[u][i].se;
		if(v != dad && !mark[v])
			sz[u] += dfs(v,u,de+1,vdi);
	}
	return sz[u];
}

void Dfs(int u) {
	nodes.clear();
	dfs(u,-1,0,0);
}

int findRoot() {
	int nsz = nodes.size();
	int root = nodes[0];
	int minSz = sz[root];
	int limit = (nsz+1) / 2;
	for( int i = 1 ; i < nsz ; i++ ) {
		int u = nodes[i];
		if(sz[u] >= limit && sz[u] < minSz) {
			root = u;
			minSz = sz[u];
		}
	}
	return root;
}

void solve(int u) {
	Dfs(u);
	u = findRoot();
	mark[u] = true;
	int deg = adj[u].size();
	vector<int> rem;
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i].fi;
		int d = adj[u][i].se;
		if(!mark[v]) {
			Dfs(v);
			vector<pi> upd;
			int nsz = nodes.size();
			for( int j = 0 ; j < nsz ; j++ ) {
				int w = nodes[j];
				int wDist = dist[w] + d;
				int wDepth = depth[w] + 1;
				if(wDist <= k) {
					rem.pb(wDist);
					upd.pb(pi(wDist,wDepth));
					int remDist = k-wDist;
					if(minDepth[remDist] != -1)
						ans = min(ans,minDepth[remDist]+wDepth);
				}
				if(wDist == k)
					ans = min(ans,wDepth);
			}
			int nupd = upd.size();
			for( int j = 0 ; j < nupd ; j++ ) {
				int key = upd[j].fi;
				int val = upd[j].se;
				if(minDepth[key] == -1 || val < minDepth[key])
					minDepth[key] = val;
			}
		}
	}
	int r = rem.size();
	for( int i = 0 ; i < r ; i++ )
		minDepth[rem[i]] = -1;
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i].fi;
		if(!mark[v])
			solve(v);
	}
}

int best_path(int N, int K, int e[][2], int c[]) {
	n = N;
	k = K;
	ans = n+1;
	for( int i = 0 ; i < n-1 ; i++ ) {
		int u = e[i][0];
		int v = e[i][1];
		int d = c[i];
		adj[u].pb(pi(v,d));
		adj[v].pb(pi(u,d));
	}
	memset(minDepth,-1,sizeof(minDepth));
	solve(0);
	return (ans < n) ? ans : -1;
}

/*
int main() {
	int n = 11 , k = 12;
	int e[10][2];
	e[0][0] = 0 , e[0][1] = 1;
	e[1][0] = 0 , e[1][1] = 2;
	e[2][0] = 2 , e[2][1] = 3;
	e[3][0] = 3 , e[3][1] = 4;
	e[4][0] = 4 , e[4][1] = 5;
	e[5][0] = 0 , e[5][1] = 6;
	e[6][0] = 6 , e[6][1] = 7;
	e[7][0] = 6 , e[7][1] = 8;
	e[8][0] = 8 , e[8][1] = 9;
	e[9][0] = 8 , e[9][1] = 10;
	int d[10];
	d[0] = 3;
	d[1] = 4;
	d[2] = 5;
	d[3] = 4;
	d[4] = 6;
	d[5] = 3;
	d[6] = 2;
	d[7] = 5;
	d[8] = 6;
	d[9] = 999;
	printf("%d\n",best_path(n,k,e,d));
	return 0;
}
*/

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