제출 #105923

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

race

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

using namespace std;

const int MAX_N = 200000;

vector<pair<int, int> > graph[MAX_N];
set<pair<long long, int> > chains[MAX_N];
long long lazy[MAX_N];
int lazyedge[MAX_N];
int rez = MAX_N + 1;

int subtree[MAX_N];

void predfs(int nod, int papa = -1) {
	subtree[nod]++;
	for(auto it: graph[nod])
		if(it.first != papa) {
			predfs(it.first, nod);
			subtree[nod] += subtree[it.first];
		}
}

void solvedfs(int nod, int k, int papa = -1) {
	int heavySon = -1;

	for(auto it: graph[nod])
		if(it.first != papa && (heavySon == -1 || (heavySon != -1 && subtree[it.first] > subtree[heavySon])))
			heavySon = it.first;
	
	for(auto it: graph[nod])
		if(it.first != papa) {
			solvedfs(it.first, k, nod);
			lazy[it.first] += it.second;
			lazyedge[it.first]++;
		}
	
	if(heavySon != -1) {
		// Toarna chestii in heavySon
		chains[nod].swap(chains[heavySon]);
		swap(lazy[nod], lazy[heavySon]);
		swap(lazyedge[nod], lazyedge[heavySon]);

		for(auto it: graph[nod])
			if(it.first != papa && it.first != heavySon) {
				for(auto ch: chains[it.first]) {
					set<pair<long long, int> >::iterator lb;
					lb = chains[nod].lower_bound(make_pair(k - (ch.first + lazy[it.first]) - lazy[nod], -MAX_N-1));
					if(lb != chains[nod].end() && lb->first + ch.first + lazy[it.first] + lazy[nod] == k)
						rez = min(rez, ch.second + lb->second + lazyedge[it.first] + lazyedge[nod]);
				}
				
				for(auto ch: chains[it.first]) {
					chains[nod].insert(make_pair(ch.first + lazy[it.first] - lazy[nod], ch.second + lazyedge[it.first] - lazyedge[nod]));
				}
			}
	}

	set<pair<long long, int> >::iterator lb;
	lb = chains[nod].lower_bound(make_pair(k - lazy[nod], -MAX_N-1));
	if(lb != chains[nod].end() && lb->first + lazy[nod] == k)
		rez = min(rez, lb->second + lazyedge[nod]);
	
	chains[nod].insert(make_pair(-lazy[nod], -lazyedge[nod]));
}

int best_path(int N, int K, int H[][2], int L[]) {
  for(int i = 0; i < N - 1; ++i)
		for(int j = 0; j < 2; ++j)
			graph[H[i][j]].push_back(make_pair(H[i][0] ^ H[i][1] ^ H[i][j], L[i]));
	
	predfs(0);
	solvedfs(0, K);

	if(rez == MAX_N + 1)
		return -1;
	return rez;
}

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