Submission #237845

#	Time	Username	Problem	Language	Result	Execution time	Memory
237845		T0p_	Race (IOI11_race)	C++14	0 / 100	18 ms	21248 KiB

race

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

#define pb push_back

struct EDGE
{
	int node;
	long long weight;
};

int N, K;
int lv[200002], sz[200002];
int ans = 1e9;
long long jmp[2][20][200002];
vector<int> gc[200002];
vector<EDGE> g[200002];
bool visit[200002];
unordered_map<int, int> mp[200002];

void dfs1(int u, int p)
{
	lv[u] = p;
	for(auto x : g[u])
	{
		if(lv[x.node]) continue ;
		jmp[0][0][x.node] = u;
		jmp[1][0][x.node] = x.weight;
		dfs1(x.node, p+1);
	}
}

int get_sz(int u, int p)
{
	sz[u] = 1;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		sz[u] += get_sz(x.node, u);
	}
	return sz[u];
}

int get_centroid(int u, int p, int n)
{
	bool ch = (n - sz[u] <= n/2) ? true : false;
	int nn = 0, nf = 0;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		if(sz[x.node] > n/2)
		{
			ch = false;
			if(sz[x.node] > nf)
			{
				nn = x.node;
				nf = sz[x.node];
			}
		}
	}
	return (ch) ? u : get_centroid(nn, u, n);
}

int build(int u, int p)
{
	int n = get_sz(u, p);
	int c = get_centroid(u, p, n);
	visit[c] = true;
	for(auto x : g[c])
	{
		if(visit[x.node]) continue ;
		gc[c].pb(build(x.node, c));
	}
	return c;
}

pair<int, int> finddis(int u, int v)
{
	if(lv[u] < lv[v]) swap(u, v);
	int r1 = 0, r2 = 0;
	for(int i=19 ; i>=0 ; i--)
		if(lv[jmp[0][i][u]] >= lv[v])
		{
			r1 += (1<<i);
			r2 += jmp[1][i][u];
			u = jmp[0][i][u];
		}
	if(u == v) return {r1, r2};
	for(int i=19 ; i>=0 ; i--)
		if(jmp[0][i][u] != jmp[0][i][v])
		{
			r1 += (1<<(i+1));
			r2 += jmp[1][i][u] + jmp[1][i][v];
			u = jmp[0][i][u], v = jmp[0][i][v];
		}
	return {r1 + 2, r2 + jmp[1][0][u] + jmp[1][0][v]};

}
void dfs2(int u)
{
	for(auto x : gc[u])
	{
		dfs2(x);
		pair<int, int> dis = finddis(u, x);
		for(auto y : mp[x])
			if(mp[u].count(K-y.first-dis.second)) ans = min(ans, mp[u][K-y.first-dis.second] + y.second + dis.first);
		for(auto y : mp[x])
			if(y.first + dis.second <= K)
			{
				if(mp[u].count(y.first+dis.second)) mp[u][y.first+dis.second] = min(mp[u][y.first+dis.second], y.second+dis.first);
				else mp[u][y.first+dis.second] = y.second + dis.first;
			} 
		mp[x].clear();
	}
	if(mp[u].count(K)) ans = min(ans, mp[u][K]);
	mp[u][0] = 0;
}

int best_path(int n, int k, int h[][2], int l[])
{
	N = n, K = k;
	for(int i=0 ; i<n-1 ; i++)
	{
		g[h[i][0]+1].pb({h[i][1]+1, l[i]});
		g[h[i][1]+1].pb({h[i][0]+1, l[i]});
	}
	dfs1(1, 1);
	for(int i=1 ; i<20 ; i++)
		for(int j=1 ; j<=n ; j++)
		{
			jmp[0][i][j] = jmp[0][i-1][jmp[0][i-1][j]];
			jmp[1][i][j] = jmp[1][i-1][j] + jmp[1][i-1][jmp[0][i-1][j]];
		}
	dfs2(build(1, 0));
	return (ans == 1e9) ? -1 : ans;
}

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