제출 #475689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475689		AdamGS	경주 (Race) (IOI11_race)	C++14	100 / 100	539 ms	36460 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, MAXK=1e6+7;
vector<pair<int,int>>V[LIM];
int usuniete[LIM], ile[LIM], rozmiar, ans, n, k, nr;
pair<int,int>T[MAXK];
queue<int>q;
void DFS(int x, int o) {
	q.push(x);
	++rozmiar;
	ile[x]=1;
	for(auto i : V[x]) if(i.st!=o && !usuniete[i.st]) {
		DFS(i.st, x);
		ile[x]+=ile[i.st];
	}
}
int znajdz(int x) {
	rozmiar=0;
	DFS(x, x);
	int ma=LIM, cent=-1;
	while(!q.empty()) {
		int p=q.front(), akt=rozmiar-ile[p]; q.pop();
		for(auto i : V[p]) if(!usuniete[i.st]) {
			if(ile[i.st]<ile[p]) akt=max(akt, ile[i.st]);
		}
		if(akt<ma) {
			ma=akt;
			cent=p;
		}
	}
	return cent;
}
void licz(int x, int o, int v, int g) {
	if(v>k) v=k+1;
	if(v<=k && T[k-v].nd==nr) {
		ans=min(ans, T[k-v].st+g);
	}
	for(auto i : V[x]) if(i.st!=o && !usuniete[i.st]) licz(i.st, x, v+i.nd, g+1);
}
void ustaw(int x, int o, int v, int g) {
	if(v>k) v=k+1;
	if(v<=k) {
		if(T[v].nd<nr || T[v].st>g) T[v]={g, nr};
	}
	for(auto i : V[x]) if(i.st!=o && !usuniete[i.st]) ustaw(i.st, x, v+i.nd, g+1);
}
void cd(int x) {
	int p=znajdz(x);
	usuniete[p]=1;
	++nr;
	T[0]={0, nr};
	for(auto i : V[p]) if(!usuniete[i.st]) {
		licz(i.st, p, i.nd, 1);
		ustaw(i.st, p, i.nd, 1);
	}
	for(auto i : V[p]) if(!usuniete[i.st]) cd(i.st);
}
int best_path(int N, int K, int h[][2], int l[]) {
	n=N; k=K;
	rep(i, n-1) {
		V[h[i][0]].pb({h[i][1], l[i]});
		V[h[i][1]].pb({h[i][0], l[i]});
	}
	ans=LIM;
	cd(0);
	if(ans==LIM) return -1;
	return ans;
}

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