Submission #997661

#	Time	Username	Problem	Language	Result	Execution time	Memory
997661		blacktulip	Race (IOI11_race)	C++17	100 / 100	308 ms	51800 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define endl "\n"
#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)
#define _ << " " <<

const int li = 1000005;

vector<pair<int,int>> v[li];
int k;
int sub[li],cnt[li],vis[li];
int cev=0,siz;

inline void dfs(int node,int ata){
	sub[node]=1;
	for(auto go:v[node]){
		if(go.fi==ata)continue;
		if(vis[go.fi])continue;
		dfs(go.fi,node);
		sub[node]+=sub[go.fi];
	}
}

inline int find_centroid(int node,int ata){
	for(auto go:v[node]){
		if(go.fi==ata)continue;
		if(vis[go.fi])continue;
		if(sub[go.fi]>=siz/2)return find_centroid(go.fi,node);
	}
	return node;
}

inline void calc(int node,int ata,int dep,int say){
	if(dep>k)return ;
	cev=min(cev,cnt[k-dep]+say);
	//~ cout<<dep<<" () "<<say<<" :: "<<cnt[k-dep]<<" :: "<<cnt[dep]<<endl;
	for(auto go:v[node]){
		if(go.fi==ata)continue;
		if(vis[go.fi])continue;
		calc(go.fi,node,dep+go.se,say+1);
	}
}

inline void increase(int node,int ata,int dep,int val){
	if(dep>k)return ;
	if(val>=1000000000)cnt[dep]=1000000000;
	else cnt[dep]=min(1000000000,min(cnt[dep],val));
	for(auto go:v[node]){
		if(go.fi==ata)continue;
		if(vis[go.fi])continue;
		increase(go.fi,node,dep+go.se,val+1);
	}
}

inline void solve(int c){
	dfs(c,-1);
	siz=sub[c];
	c=find_centroid(c,-1);//artik c centroid
	//~ cout<<c<<" () "<<cev<<endl;
	vis[c]=1;
	cnt[0]=0;
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		calc(go.fi,c,go.se,1);
		increase(go.fi,c,go.se,1);
	}
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		increase(go.fi,c,go.se,1000000000);
	}
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		solve(go.fi);
	}
	
}

int best_path(int n, int K, int h[][2], int l[]){
	k=K;
	for(int i=0;i<=k;i++)cnt[i]=1000000000;
	for(int i=0;i<n-1;i++){
		v[h[i][0]].pb({h[i][1],l[i]});
		v[h[i][1]].pb({h[i][0],l[i]});
	}
	cev=1000000000;
	solve(0);
	if(cev==1000000000)cev=-1;
	return cev;
}

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