Submission #171294

#	Time	Username	Problem	Language	Result	Execution time	Memory
171294		nafis_shifat	경주 (Race) (IOI11_race)	C++14	0 / 100	43 ms	38260 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]={};

int ans=mxn;
int K;

vector<int> centree[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);
			
			centree[c].push_back(d);
		
			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]);
        }
    }
}
map<int,int> mp[mxn];
void pans(int cur,int rt)
{
    int d=pathn(cur,rt);
    ll dst=getdist(cur,rt);
    if(dst<=K)
    {
        if(mp[rt].find(K-dst)!=mp[rt].end())
        {
            ans=min(ans,(d+mp[rt][K-dst]));
        }
    }
    for(int i:centree[cur])pans(i,rt);
}


void update(int cur,int rt)
{
    
    int d=pathn(cur,rt);
    ll dst=getdist(cur,rt);
    if(dst<=K)
    {
        if(mp[rt].find(dst)==mp[rt].end())mp[rt][dst]=d;
        else mp[rt][dst]=min(d,mp[rt][dst]);
        
    }
    
    for(int i:centree[cur])update(i,rt);
    
}


void df(int cur)
{
    for(int i:centree[cur])
    {
        pans(i,cur);
        update(i,cur);
    }
}


int best_path(int N, int k, int H[][2], int L[])
{
    K=k;
	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);
	
	for(int i=0;i<N;i++)df(i);
	
	return ans==mxn?-1:ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs2(int, int, int)':
race.cpp:171:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[cur].size();i++)
                 ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:249:6: warning: unused variable 'r' [-Wunused-variable]
  int r=build(0);
      ^

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