Submission #877805

#	Time	Username	Problem	Language	Result	Execution time	Memory
877805		mahmoudbadawy	Race (IOI11_race)	C++17	43 / 100	1194 ms	83976 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int N=200005;

vector< pair<int,int> > adj[N];
vector<int> adjj[N];
long long sz[N],dp[N][20],par[N],hi[N],dis[N];
int del[N];
int nn;
long long anss=(1<<30);

void dfs(int x,int pa)
{
	dp[x][0]=pa;
	if(pa!=-1) hi[x]=hi[pa]+1;
	else hi[x]=0;
	for(int i=1;i<20;i++)
		dp[x][i]=dp[dp[x][i-1]][i-1];
	int cur=0;
	for(auto it=adj[x].begin();it!=adj[x].end();it++)
	{
		if((*it).first != pa) {dis[(*it).first]=dis[x]+(*it).second; dfs((*it).first,x); cur++;}
	}
}

void dfs2(int x,int pa)
{
	sz[x]=1;
	nn++;
	for(auto it=adj[x].begin();it!=adj[x].end();it++)
	{
		if((*it).first == pa || del[(*it).first]) continue;
		dfs2((*it).first,x);
		sz[x]+=sz[(*it).first];
	}
}

int getcentroid(int x,int pa)
{
	for(auto it=adj[x].begin();it!=adj[x].end();it++)
	{
		if((*it).first == pa || del[(*it).first]) continue;
		if(sz[(*it).first]>nn/2)
			return getcentroid((*it).first,x);
	}
	return x;
}

int lca(int x,int y)
{
	if(hi[x]<hi[y]) swap(x,y);
	for(int i=19;i>=0;i--)
		if(hi[x]-(1<<i)>=hi[y])
			x=dp[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i]; y=dp[y][i];
		}
	}
	return dp[x][0];
}

int gethi(int x,int y)
{
	return hi[x]+hi[y]-2*hi[lca(x,y)];
}

long long getdis(int x,int y)
{
	return dis[x]+dis[y]-2*dis[lca(x,y)];
}

int ans[1000006];

void go(int x,int pa,int K,int root)
{
	long long z=getdis(x,root);
	if(z<=K)
		anss=min(anss,1LL*ans[K-z]+gethi(x,root));
	for(auto it=adj[x].begin();it!=adj[x].end();it++)
	{
		if((*it).first == pa || del[(*it).first]) continue;
		go((*it).first,x,K,root);
	}
	if(z<=K)
		ans[z]=min(ans[z],gethi(x,root));
}

void clear(int x,int pa,int K,int root)
{
	long long z=getdis(x,root);
	if(z<=K)
		ans[K-z]=(1<<30);
	for(auto it=adj[x].begin();it!=adj[x].end();it++)
	{
		if((*it).first == pa || del[(*it).first]) continue;
		clear((*it).first,x,K,root);
	}
	if(z<=K)
		ans[z]=(1<<30);
}

int maxil=0;

void decompose(int x,int pa,int K,int lev=0)
{
	nn=0;
	dfs2(x,-1);
	int centroid=getcentroid(x,-1);
	//cout << x << " " << centroid << " " << nn << endl;
	if(pa==-1) pa=centroid;
	par[centroid]=pa;
	clear(centroid,-1,K,centroid);
	ans[0]=0;
	go(centroid,-1,K,centroid);
	del[centroid]=1;
	maxil=max(maxil,lev);
	for(auto it=adj[centroid].begin();it!=adj[centroid].end();it++)
	{
		if(del[(*it).first]) continue;
		decompose((*it).first,centroid,K,lev+1);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	for(int i=0;i<N-1;i++)
	{
		int x=H[i][0],y=H[i][1],l=L[i];
		adj[x].push_back({y,l});
		adjj[x].push_back(y);
		adj[y].push_back({x,l});
		adjj[y].push_back(x);
	}
	dfs(0,-1);
	decompose(0,-1,K);	
	//cout << gethi(90,74-12) << " " << gethi(90,74)+gethi(74,74-12) << endl;
	/*for(int i=0;i<N;i++)
	{
		int x=i;
		cout << x << ": \n";
		while(1)
		{
			long long aa=getdis(x,i),bb=gethi(x,i);
			if(ans[x].find(K-aa)!=ans[x].end())
			{
				anss=min(anss,bb+ans[x][K-aa]);
				if(bb+ans[x][K-aa]==28)
				{
					cout << i << " " << x << " " << ans[x][K-aa] << endl;
				}
			}
			if(aa<=K){
				long long z=(ans[x].find(aa)==ans[x].end()?(1<<30):ans[x][aa]);
				ans[x][aa]=min(z,bb);
			}
			if(bb==12)
			{
				cout << i << " " << x << " " << aa << " " << bb << " :HERE " << endl;
			}
			if(x==par[x]) break;
			x=par[x];
			cout << x << endl;
		}
	}*/
	return (anss==(1<<30)?-1:anss);
}

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