Submission #171441

#	Time	Username	Problem	Language	Result	Execution time	Memory
171441		nafis_shifat	Race (IOI11_race)	C++14	100 / 100	982 ms	45808 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;
const int mexa=1e6+10;
vector<int> tree[mxn];
vector<int> cost[mxn];
int subsz[mxn];
int centroidMarked[mxn]={};

int parent[mxn]={};

int ans=mxn;
int K;


int cnt[mexa];

vector<int> csts;

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;

}

void pans(int cur,int prev,int dst,int d)
{
    if(dst>K)return;
    ans=min(ans,d+cnt[K-dst]);
   // cout<<K-dst<<" hehe "<<cur<<endl;
    for(int i=0;i<tree[cur].size();i++)
    {
        int v=tree[cur][i];
        if(!centroidMarked[v] && v!=prev)
        {
            pans(v,cur,dst+cost[cur][i],d+1);
        }
    }
}


void update(int cur,int prev,int dst,int d)
{
    if(dst>K)return;
    cnt[dst]=min(d,cnt[dst]);
    csts.push_back(dst);
    for(int i=0;i<tree[cur].size();i++)
    {
        int v=tree[cur][i];
        
        if(!centroidMarked[v] && v!=prev)
        {
            update(v,cur,dst+cost[cur][i],d+1);
        }
    }
}

void df(int root)
{
	int c=getCentroid(root);
	//cout<<c<<endl;
	for(int i:csts)cnt[i]=mxn;
	csts.clear();
	cnt[0]=0;
	
	

	for(int i=0;i<tree[c].size();i++)
	{
	    int v=tree[c][i];
	    
		if(!centroidMarked[v])
		{
			pans(v,c,cost[c][i],1);
			update(v,c,cost[c][i],1);
		}
	}
	
	for(int i:tree[c])
	{
	    if(!centroidMarked[i])df(i);
	}

}




int best_path(int N, int k, int H[][2], int L[])
{
    for(int i=0;i<mexa;i++)cnt[i]=mxn;
    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]);



	}

    df(0);
  
	return ans==mxn?-1:ans;
}

Compilation message (stderr)

race.cpp: In function 'void pans(int, int, int, int)':
race.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[cur].size();i++)
                 ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void update(int, int, int, int)':
race.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[cur].size();i++)
                 ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void df(int)':
race.cpp:111:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[c].size();i++)
              ~^~~~~~~~~~~~~~~

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