Submission #848480

#	Time	Username	Problem	Language	Result	Execution time	Memory
848480		blacktulip	Race (IOI11_race)	C++14	100 / 100	515 ms	72860 KiB

race

#include <bits/stdc++.h>
#include "race.h"
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
//~ #define int long long
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 100000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 1000005;
const lo mod = 1000000007;
 
lo n,m,b[li],a[li],k,flag,t,sub[li],vis[li],cevap=inf,say,last[li],visit[li];
lo cev;
//~ unordered_map<lo,lo> last,visit;
string s;
vector<PII> v[li];
 
void boya(int node,int ata,lo co){
	if(co<=k){
		visit[co]=0;
		visit[k-co]=0;
	}
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i].fi;
		if(go==ata)continue;
		if(vis[go]==1)continue;
		boya(go,node,co+v[node][i].se);
	}
	if(co<=k){
		visit[co]=0;
		visit[k-co]=0;
	}
}
 
void dfs(lo node,lo ata){
	sub[node]=1;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i].fi;
		if(go==ata)continue;
		if(vis[go]==1)continue;
		dfs(go,node);
		sub[node]+=sub[go];
	}
}
 
lo find_centroid(lo node,lo ata,lo sz){
	//~ int mx=0;
	//~ int ind=0;
	for(lo i=0;i<(lo)v[node].size();i++){
		int go=v[node][i].fi;
		if(vis[go]==1)continue;
		if(go==ata)continue;
		if(sub[go]>=(sz)/2)return find_centroid(go,node,sz);
	}
	return node;
}
 
void dfs2(lo node,lo ata,lo der,lo co){
	for(lo i=0;i<(lo)v[node].size();i++){
		lo go=v[node][i].fi;
		if(go==ata)continue;
		if(vis[go]==1)continue;
		dfs2(go,node,der+1,co+v[node][i].se);
		
	}
	if(co<=k){
		if(visit[k-co]==1){
			cevap=min(cevap,last[k-co]+der);
		}
	}
}
 
void dfs1(lo node,lo ata,lo der,lo co){
	for(lo i=0;i<(lo)v[node].size();i++){
		lo go=v[node][i].fi;
		if(go==ata)continue;
		if(vis[go]==1)continue;
		dfs1(go,node,der+1,co+v[node][i].se);
		
	}
	if(co<=k){
		if(visit[co]==0)last[co]=der;
		visit[co]=1;
		last[co]=min(last[co],der);
	}
	
}
 
void solve(lo node){
	//~ say++;
	//~ cout<<say<<endl;
	
	//~ FOR	 sub[node]=0;
	//~ last.clear();
	//~ for(int i=0;i<=k;i++)visit[i]=0;
	dfs(node,-1);
	
	lo c=find_centroid(node,-1,sub[node]);
	boya(c,-1,0);
	for(lo i=0;i<(lo)v[c].size();i++) {
		
		int go=v[c][i].first;
		
		if(vis[go]) continue ;
		
		dfs2(go,c,1,v[c][i].second);
		dfs1(go,c,1,v[c][i].second);
		
	}
	if(visit[k]==1)
		cevap=min(cevap,last[k]);
	vis[c]=1;
	//~ cout<<c<<endl;
	//~ dfs()
	for(lo i=0;i<(lo)v[c].size();i++){
		if(vis[v[c][i].fi]==0)solve(v[c][i].fi);
	}
	
}
 
 
int best_path(int N, int K, int H[][2], int L[])
{
	n=N;
	k=K;
	//~ scanf("%lld %lld",&n,&k);
	for(int i=0;i<N-1;i++){
		//~ int x,y,z;
		//~ scanf("%lld %lld %lld",&x,&y,&z);
		v[H[i][0]].pb(mp(H[i][1],L[i]));
		v[H[i][1]].pb(mp(H[i][0],L[i]));
	}
	solve(0);
	if(cevap>=inf)cevap=-1;
  return cevap;
}

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