제출 #1316894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316894		exoworldgd	경주 (Race) (IOI11_race)	C++20	100 / 100	952 ms	47116 KiB

race

#include<bits/stdc++.h>
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
vector<vector<pair<ll,int>>>g;
vector<bool>dead;
vector<int>sz;
int ans=INT_MAX;
void dfs_sz(int u,int p){
	sz[u]=1;
	for(auto[w,v]:g[u])if(v^p&&!dead[v])dfs_sz(v,u),sz[u]+=sz[v];
}
int centroid(int u,int p,int comp){
	for(auto[w,v]:g[u])if(v^p&&!dead[v]&&sz[v]>comp/2)return centroid(v,u,comp);
	return u;
}
map<ll,int>mp;
vector<pair<ll,int>>vals;
void dfs(int u,int p,ll dist,int path){
	vals.push_back({dist,path});
	for(auto[w,v]:g[u])if(v^p&&!dead[v])dfs(v,u,dist+w,path+1);
}
void solve(int u,ll k){
	dfs_sz(u,-1);
	int c=centroid(u,-1,sz[u]);
	mp[0]=0;
	for(auto[w,v]:g[c]){
		if(dead[v])continue;
		dfs(v,c,w,1);
		for(auto x:vals)if(mp.count(k-x.first))ans=min(ans,x.second+mp[k-x.first]);
		for(auto x:vals){
			if(!mp.count(x.first))mp[x.first]=x.second;
			else mp[x.first]=min(mp[x.first],x.second);
		}
		vals.clear();
	}
	mp.clear(),dead[c]=1;
	for(auto[w,v]:g[c])if(!dead[v])solve(v,k);
}
int best_path(int n,int k,int h[][2],int *l){
	g=vector<vector<pair<ll,int>>>(n);
	dead=vector<bool>(n);
	sz=vector<int>(n);
	for(int i=0;i<n-1;i++)g[h[i][0]].push_back({l[i],h[i][1]}),g[h[i][1]].push_back({l[i],h[i][0]});
	solve(0,k);
	int res=ans;
	g.clear(),dead.clear(),sz.clear(),ans=INT_MAX;
	return res!=INT_MAX?res:-1;
}

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