Submission #173226

#	Time	Username	Problem	Language	Result	Execution time	Memory
173226		aer0park	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<pi,ll> pii;

ll anw=1e16,n,k,cen,del[200005],sz[200005];
pi pth[200005];
map<pi,ll> l;
vector<ll> g[200005];
vector<pii> ar;

void gtsz(ll a,ll p)
{
	sz[a]=1;
	for(int i=0;i<g[a].size();i++)
		if(g[a][i]!=p&&!del[g[a][i]])
			gtsz(g[a][i],a),sz[a]+=sz[g[a][i]];
}

void fdcen(ll a,ll p,ll mxsz)
{
	ll mx=0;
	for(int i=0;i<g[a].size();i++)
		if(g[a][i]!=p&&sz[g[a][i]]>mxsz/2&&!del[g[a][i]])
			fdcen(g[a][i],a,mxsz);
	for(int i=0;i<g[a].size();i++)
		if(g[a][i]!=p&&!del[g[a][i]])
			mx=max(mx,sz[g[a][i]]);	
	if(mx<=mxsz/2) cen=a;
}

void gtpth(ll a,ll p)
{
	if(p==-1) pth[a]={0,0};
	for(int i=0;i<g[a].size();i++)
		if(g[a][i]!=p&&!del[g[a][i]])
		{
			pth[g[a][i]].f=pth[a].f+l[{a,g[a][i]}];
			pth[g[a][i]].s=pth[a].s+1;
			gtpth(g[a][i],a);
		}	
}

void push(ll a,ll p,ll id)
{
	ar.push_back({pth[a],id});
	for(int i=0;i<g[a].size();i++)
		if(g[a][i]!=p&&!del[g[a][i]])
			push(g[a][i],a,id);
}

void getanw(ll a,ll p)
{
	gtsz(a,p),fdcen(a,p,sz[a]),gtpth(cen,-1);
	a=cen,del[a]=1;
	ar.clear();
	for(int i=0;i<g[a].size();i++)
		if(g[a][i]!=p&&!del[g[a][i]])
			push(g[a][i],a,i);
	ar.push_back({pth[a],g[a].size()});
	sort(ar.begin(),ar.end());
	for(int i=0;i<ar.size();i++)
	{
		auto it=lower_bound(ar.begin(),ar.end(),pii(pi(k-ar[i].f.f,-1),-1));
		while(1)
		{
			if(it->f.f!=k-ar[i].f.f) break;
			if(it->s!=ar[i].s)
			{
				anw=min(anw,ar[i].f.s+it->f.s);
				break;
			}
			it++;
		}
	}
	for(int i=0;i<g[a].size();i++)
		if(g[a][i]!=p&&!del[g[a][i]])
			getanw(g[a][i],a);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		ll a,b,c;cin>>a>>b>>c;
		g[a].push_back(b),g[b].push_back(a);
		l[{a,b}]=c,l[{b,a}]=c;	
	}
	getanw(0,-1);
	if(anw==1e16) cout<<-1;
	else cout<<anw;
	return 0;
}

Compilation message (stderr)

race.cpp: In function 'void gtsz(ll, ll)':
race.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
race.cpp: In function 'void fdcen(ll, ll, ll)':
race.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
race.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
race.cpp: In function 'void gtpth(ll, ll)':
race.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
race.cpp: In function 'void push(ll, ll, ll)':
race.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
race.cpp: In function 'void getanw(ll, ll)':
race.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
race.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ar.size();i++)
              ~^~~~~~~~~~
race.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
/tmp/cceuOdsN.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc44GwYT.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/cc44GwYT.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status