Submission #147335

#	Time	Username	Problem	Language	Result	Execution time	Memory
147335		mosiashvililuka	Race (IOI11_race)	C++14	100 / 100	855 ms	49272 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define mk make_pair
#define pll pair <long long, long long> 
using namespace std;
long long a,b,c,d,e,pas=999999999999999999LL,k,pi,p[200009],dp[200009],cnt,dep[200009],msh[200009],koka;
bool was[200009];
vector <pair <long long, long long> > v[200009];
pair <long long, long long> z[1000009];
void dfs(long long q, long long w){
	pi++;
	p[pi]=q;
	dp[q]=1;
	msh[q]=w;
	for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w||was[(*it).first]==1) continue;
		dfs((*it).first,q);
		dp[q]+=dp[(*it).first];
	}
}
void dfs2(long long q, long long w, long long r){
	dep[q]=dep[w]+1;
	if(r<=k&&z[k-r].second==cnt){
		if(pas>dep[q]+z[k-r].first){
//		    cout<<q<<" "<<z[k-r].second<<" "<<koka<<endl;
		    pas=dep[q]+z[k-r].first;
		}
	}
	for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w||was[(*it).first]==1) continue;
		dfs2((*it).first,q,(*it).second+r);
	}
}
void dfs3(long long q, long long w, long long r){
	if(r<=k){
		if(z[r].second==cnt){
			if(z[r].first>dep[q]) z[r].first=dep[q];
		}else{
			z[r].first=dep[q];
			z[r].second=cnt;
		}
	}
	for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w||was[(*it).first]==1) continue;
		dfs3((*it).first,q,(*it).second+r);
	}
}
void rec(long long q){
	cnt++;
	pi=0;
	dfs(q,0);
	long long zx=0;
	for(long long h=1; h<=pi; h++){
		bool bo=0;
		for(vector <pll>::iterator it=v[p[h]].begin(); it!=v[p[h]].end(); it++){
		   if(was[(*it).first]==1||msh[p[h]]==(*it).first) continue;
		if(dp[(*it).first]>pi/2){
			bo=1;
			break;
		}
		}
		if(pi-dp[p[h]]>pi/2) bo=1;
		if(bo==0){
			zx=p[h];
			break;
		}
	}
	z[0].first=0;
	z[0].second=cnt;
	dep[zx]=0;koka=zx;
	for(vector <pll>::iterator it=v[zx].begin(); it!=v[zx].end(); it++){
		if(was[(*it).first]==0) dfs2((*it).first,zx,(*it).second);
		if(was[(*it).first]==0) dfs3((*it).first,zx,(*it).second);
	}
	was[zx]=1;
	for(vector <pll>::iterator it=v[zx].begin(); it!=v[zx].end(); it++){
	    if(was[(*it).first]==0) rec((*it).first);
	}
}
int best_path(int N, int K, int H[][2], int L[]){
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	//cin>>a>>k;
	a=N;k=K;
	for(b=1; b<a; b++){
		//cin>>c>>d>>e;
		c=H[b-1][0];d=H[b-1][1];e=L[b-1];
		c++;
		d++;
		v[c].push_back(mk(d,e));
		v[d].push_back(mk(c,e));
	}
	rec(1);
	if(pas==999999999999999999LL) return -1; else return pas;
	return 0;
}

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