Submission #1293343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293343		settop	경주 (Race) (IOI11_race)	C++20	21 / 100	1447 ms	327680 KiB

race

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

using namespace std;

#define ll long long
#define F first
#define S second
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
const int MAXN=2e5+10;
const int MAXL=20;

typedef pair<int,int> pii;

int ancestral[MAXN][MAXL],dp[MAXN],k,dep[MAXN];
ll sparse[MAXN][MAXL],ans=1e9;
set<pii> g[MAXN];
set<pair<ll,int>> caras[MAXN];
vector<int> child[MAXN],lista[MAXN];

void dfsini(int x,int p){
	for(auto [u,j]:g[x])
		if(u!=p){
			ancestral[u][0]=x;
			sparse[u][0]=j;
			dep[u]=dep[x]+1;
			dfsini(u,x);
		}
}

void dfs(int x,int p){
	dp[x]=1;
	for(auto[u,j]:g[x]) if(u!=p) dfs(u,x),dp[x]+=dp[u];
}

int get_centroid(int x,int p,int sub){
	for(auto [u,j]:g[x])
		if(u!=p && 2*dp[u]>sub) return get_centroid(u,x,sub);
	return x;
}

void build(int x,int p){
	dfs(x,p);
	int centroid=get_centroid(x,p,dp[x]);
	child[p].pb(centroid);
	vector<pii> adj(all(g[centroid]));

	for(auto [u,j]:adj){
		g[u].erase({centroid,j});
		g[centroid].erase({u,j});
		build(u,centroid);
	}
}

pair<ll,ll> dist(int a,int b){
	if(dep[a]<dep[b]) swap(a,b);

	ll r=0,r1=0;
	rfall(i,MAXL-1,0){
		if(dep[a]-(1<<i)>=dep[b]){
			r+=(1<<i);
			r1+=sparse[a][i];
			a=ancestral[a][i];
		}
	}

	if(a==b) return{r,r1};

	rfall(i,MAXL-1,0){
		if(ancestral[a][i]!=ancestral[b][i] && ancestral[a][i] && ancestral[b][i]){
			r+=2*(1<<i);
			r1+=sparse[a][i]+sparse[b][i];
			a=ancestral[a][i];
			b=ancestral[b][i];
		}
	}

	r+=2,r1+=sparse[a][0]+sparse[b][0];

	return{r,r1};
}

void calc(int x){
	caras[x].insert({0,0});
	lista[x].pb(x);

	for(auto u:child[x]){
		calc(u);
		for(auto i:lista[u]){
			auto d=dist(x,i);
			auto it=caras[x].lower_bound({k-d.S,-1});
			if(it!=caras[x].end() && (*it).F==k-d.S) ans=min(ans,d.F+(*it).S);
		}
		for(auto i:lista[u]){
			auto d=dist(x,i);
			caras[x].insert({d.S,d.F});
			lista[x].pb(i);
		}
	}
}

int best_path(int n, int K, int H[][2], int L[]){
  fall(i,0,n-2){
      int a=H[i][0],b=H[i][1]; a++,b++;
      g[a].insert({b,L[i]});
      g[b].insert({a,L[i]});
  }
  k=K;
  dfsini(1,0);

  fall(j,1,MAXL-1)
  	fall(i,1,n) ancestral[i][j]=ancestral[ancestral[i][j-1]][j-1],sparse[i][j]=sparse[i][j-1]+sparse[ancestral[i][j-1]][j-1];


	build(1,0);

	calc(child[0][0]);

  return(ans==1e9?-1:ans);
}

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