Submission #520298

#	Time	Username	Problem	Language	Result	Execution time	Memory
520298		new_acc	Race (IOI11_race)	C++14	100 / 100	670 ms	52008 KiB

race

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
vector<pair<int,int> >graf[N];
int pod[N];
pair<pair<int,int>,pair<int,int> >t[1000*1000+10];
bool vis[N];
int cn;
int res=INT_MAX;
int dfspod(int v,int o){
	int res=0;
	for(auto u:graf[v]){
		if(vis[u.fi]||u.fi==o) continue;
		res+=dfspod(u.fi,v);
	}	
	return res+1;
}
void dfs(int v,int o,int s){
	bool b=1;
	pod[v]=0;
	for(auto u:graf[v]){
		if(vis[u.fi]||o==u.fi) continue;
		dfs(u.fi,v,s);
		pod[v]+=pod[u.fi];
		if(pod[u.fi]>s/2) b=0;
	}
	pod[v]++;
	if(s-pod[v]>s/2) b=0;
	if(b) cn=v;
} 
void dfs2(int v,int o,int g,int odl,bool b,int k){
	if(g>1000*1000) return;
	if(b==0) t[g].fi.fi=0,t[g].fi.se=0,t[g].se.fi=0,t[g].se.se=0;
	else if(t[g].fi.fi>odl||t[g].fi.fi==0) t[g].fi={odl,k};
	for(auto u:graf[v]){
		if(vis[u.fi]||o==u.fi) continue;
		dfs2(u.fi,v,g+u.se,odl+1,b,k);
	}
}
void dfs3(int v,int o,int g,int odl,int k){
	if(g>1000*1000) return;
	if(t[g].fi.se!=k&&(t[g].se.fi>odl||t[g].se.fi==0)) t[g].se={odl,k};
	for(auto u:graf[v]){
		if(vis[u.fi]||o==u.fi) continue;
		dfs3(u.fi,v,g+u.se,odl+1,k);
	}	
}
void dfs_wyn(int v,int o,int g,int odl,int k,int kk){
	if(g>k) return;
	if(g==k) res=min(res,odl);
	if(t[k-g].fi.se!=kk&&t[k-g].fi.fi!=0) res=min(res,t[k-g].fi.fi+odl);
	if(t[k-g].se.se!=kk&&t[k-g].se.fi!=0) res=min(res,t[k-g].se.fi+odl);
	for(auto u:graf[v]){
		if(vis[u.fi]||o==u.fi) continue;
		dfs_wyn(u.fi,v,g+u.se,odl+1,k,kk);
	}
}
void decomp(int v,int k){
	if(vis[v]) return;
	int s=dfspod(v,v);
	dfs(v,v,s);
	for(auto u:graf[cn]){
		if(vis[u.fi]) continue;
		dfs2(u.fi,cn,u.se,1,1,u.fi);
	}
	for(auto u:graf[cn]){
		if(vis[u.fi]) continue;
		dfs3(u.fi,cn,u.se,1,u.fi);
	}
	for(auto u:graf[cn]){
		if(vis[u.fi]) continue;
		dfs_wyn(u.fi,cn,u.se,1,k,u.fi);
	}
	for(auto u:graf[cn]){
		if(vis[u.fi]) continue;
		dfs2(u.fi,cn,u.se,1,0,u.fi);
	}
	int cc=cn;
	vis[cc]=1;
	for(auto u:graf[cc]) decomp(u.fi,k);
}
int best_path(int n,int k,int h[][2],int l[]){
	for(int i=0;i<=n-2;i++) h[i][0]++,h[i][1]++,graf[h[i][0]].push_back({h[i][1],l[i]}),graf[h[i][1]].push_back({h[i][0],l[i]});
	decomp(1,k);
	if(res==INT_MAX) return -1;
	return res;
}

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