Submission #749897

#	Time	Username	Problem	Language	Result	Execution time	Memory
749897		StefanSebez	Race (IOI11_race)	C++14	100 / 100	1956 ms	48204 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int N=2*1e5+50;
const int inf=1e9+50;
vector<pair<int,int> >E[N];
bool bul[N];
int sz[N],parent[N],root,dist[N],depth[N];
int res=inf,k;
map<int,int>mapa;
void DFS(int u)
{
	sz[u]=1;
	for(auto i:E[u])
	{
		if(i.first!=parent[u] && bul[i.first]==false)
		{
			parent[i.first]=u;
			DFS(i.first);
			sz[u]+=sz[i.first];
		}
	}
}
int DFSc(int u)
{
	int ind,maks=0;
	for(auto i:E[u])
	{
		if(i.first!=parent[u] && bul[i.first]==false && sz[i.first]>maks)
		{
			maks=sz[i.first];
			ind=i.first;
		}
	}
	if(maks*2>sz[root])
	{
		return DFSc(ind);
	}
	else
	{
		return u;
	}
}
void DFSdist(int u,int w)
{
	dist[u]=dist[parent[u]]+w;
	depth[u]=depth[parent[u]]+1;
	if(k-dist[u]==0)
	{
		res=min(res,depth[u]);
	}
	else if(k-dist[u]>0 && mapa[k-dist[u]]!=0)
	{
		res=min(res,depth[u]+mapa[k-dist[u]]);
	}
	for(auto i:E[u])
	{
		if(i.first!=parent[u] && bul[i.first]==false)
		{
			DFSdist(i.first,i.second);
		}
	}
}
void DFSadd(int u)
{
	if(mapa[dist[u]]==0)
	{
		mapa[dist[u]]=depth[u];
	}
	else
	{
		mapa[dist[u]]=min(mapa[dist[u]],depth[u]);
	}
	for(auto i:E[u])
	{
        if(i.first!=parent[u] && bul[i.first]==false)
		{
			DFSadd(i.first);
		}
	}
}
void DFSclear(int u)
{
	sz[u]=0;
	dist[u]=0;
	depth[u]=0;
	for(auto i:E[u])
	{
		if(i.first!=parent[u] && bul[i.first]==false)
		{
			DFSclear(i.first);
		}
	}
	parent[u]=-1;
}
void cdecomp(int u)
{
	root=u;
	DFS(u);
	int cent=DFSc(u);
	DFSclear(u);
	/*for(int i=0;i<=N;i++)
	{
		parent[i]=-1;
	}*/
	DFS(cent);
	for(auto i:E[cent])
	{
		if(bul[i.first]==false)
		{
			DFSdist(i.first,i.second);
			DFSadd(i.first);
		}
	}
	DFSclear(cent);
	/*for(int i=0;i<=N;i++)
	{
		parent[i]=-1;
	}*/
	mapa.clear();
	bul[cent]=true;
	for(auto i:E[cent])
	{
		if(bul[i.first]==false)
		{
			cdecomp(i.first);
		}
	}
}
int best_path(int n, int K, int H[][2], int L[])
{
	k=K;
	for(int i=0;i<n-1;i++)
	{
		E[H[i][0]].push_back({H[i][1],L[i]});
		E[H[i][1]].push_back({H[i][0],L[i]});
	}
	for(int i=0;i<=n+50;i++)
	{
		parent[i]=-1;
	}
	cdecomp(0);
	if(res==inf)
	{
		res=-1;
	}
	return res;
}

Compilation message (stderr)

race.cpp: In function 'int DFSc(int)':
race.cpp:29:23: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |   if(i.first!=parent[u] && bul[i.first]==false && sz[i.first]>maks)
      |               ~~~~~~~~^

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