Submission #171223

#	Time	Username	Problem	Language	Result	Execution time	Memory
171223		nafis_shifat	Race (IOI11_race)	C++14	0 / 100	24 ms	24056 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=2e5+9;
vector<int> tree[mxn];
vector<int> cost[mxn];
int subsz[mxn];
int centroidMarked[mxn]={};

int level[mxn]={};


int pa[18][mxn];

ll dist[18][mxn];

int parent[mxn]={};

void initLCA(int n)
{
	for(int i=1;i<18;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(pa[i-1][j]!=-1)
			{
				pa[i][j]=pa[i-1][pa[i-1][j]];
				dist[i][j]=dist[i-1][j]+dist[i-1][pa[i-1][j]];
			}
		}
	}
}


int findlca(int u,int v)
{
	if(level[u]<level[v])swap(u,v);

	int diff=level[u]-level[v];
	for(int i=0;i<18;i++)
	{
		if((diff>>i)&1)u=pa[i][u];
	}

	if(u==v)return u;


	for(int i=17;i>=0;i--)
	{
		if(pa[i][u]!=pa[i][v])
		{
			u=pa[i][u];
			v=pa[i][v];
		}
	}

	return pa[0][u];
}




int pathn(int u,int v)
{
	int lca=findlca(u,v);
	return level[u]-level[lca]+level[v]-level[lca];
}



ll td(int u,int lca)
{
	int diff=level[u]-level[lca];
	ll r=0;
	for(int i=0;i<18;i++)
	{
		if((diff>>i)&1)
		{
			r+=dist[i][u];
			u=pa[i][u];
		}
	}
	return r;
}

ll getdist(int u,int v)
{
	int lca=findlca(u,v);
	return td(u,lca)+td(v,lca);
}
void dfs(int cur,int prev)
{
	subsz[cur]=1;
	
	for(int i:tree[cur])
	{
	
		if(i!=prev && !centroidMarked[i])
		{
			dfs(i,cur);
			subsz[cur]+=subsz[i];
		}
	}
}

int getCentroid(int cur,int prev,int sz)
{
	bool isC=true;
	int hc=-1;
	for(int i:tree[cur])
	{
		if(i!=prev && !centroidMarked[i] && subsz[i]>sz)
		{
			hc=i;
			isC=false;
			break;
		}
	}


	if(isC && subsz[cur]>=sz)return cur;

	return getCentroid(hc,cur,sz);
}


int getCentroid(int src)
{
	dfs(src,-1);
	int c=getCentroid(src,-1,subsz[src]/2);
	centroidMarked[c]=1;
	return c;

}



int build(int root)
{
	int c=getCentroid(root);

	for(int i:tree[c])
	{
		if(!centroidMarked[i])
		{
			int d=build(i);
		
			parent[d]=c;
		}
	}
	return c;
}




void dfs2(int cur,int prev,int cst)
{
    level[cur]=level[prev]+1;
    pa[0][cur]=prev;
    dist[0][cur]=cst;
    
    for(int i=0;i<tree[cur].size();i++)
    {
        int v=tree[cur][i];
        if(v!=prev)
        {
            dfs2(v,cur,cost[cur][i]);
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    
	for(int i=0;i<N-1;i++)
	{
		tree[H[i][0]].push_back(H[i][1]);
		tree[H[i][1]].push_back(H[i][0]);

		cost[H[i][0]].push_back(L[i]);
		cost[H[i][1]].push_back(L[i]);



	}
	


	memset(pa,-1,sizeof(pa));
	
	dfs2(0,0,0);
	


	initLCA(N);


	int r=build(0);
	parent[r]=-1;
	int ans;

	int cnt[6*mxn];
	cnt[0]=0;
	 ans=mxn;
	for(int i=1;i<=K;i++)cnt[i]=mxn;
	


	for(int i=0;i<N;i++)
	{
		int u=i;
		while(u!=-1)
		{
			ll d=getdist(i,u);
			if(d>K)
			{
			    u=parent[u];
			    continue;
			    
			}

			int pn=pathn(i,u);

			ans=min(ans,pn+cnt[K-d]);
			cnt[d]=min(cnt[d],pn);

			u=parent[u];


		}
	}

	if(ans==mxn)return -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs2(int, int, int)':
race.cpp:165:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[cur].size();i++)
                 ~^~~~~~~~~~~~~~~~~

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