Submission #405142

#	Time	Username	Problem	Language	Result	Execution time	Memory
405142		AugustinasJucas	경주 (Race) (IOI11_race)	C++14	100 / 100	873 ms	37844 KiB

race

#include "race.h"
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
//#include "race.h"
const int dydis = 2e5 + 10;
vector<pair<int, int> > gr[dydis];
int n, k;
bool vis[dydis] = {};
int tevas[dydis];
vector<int> visi;
int sz[dydis];
int ans = inf;
void dfs(int v, int came){
	tevas[v] = came;
	visi.push_back(v);
	sz[v] = 1;
	for(auto x : gr[v]){
		if(x.first == came) continue;
		dfs(x.first, v);
		sz[v] += sz[x.first];
	}
}
int findCentroid(int v){
	visi.clear();
	dfs(v, v);
	
	for(auto x : visi){
		int mx = 0;
		int sm = 0;
		for(int i = 0; i < (int)gr[x].size(); i++){
			if(gr[x][i].first == tevas[x]) continue;
			mx = max(mx, sz[gr[x][i].first]);
			sm += sz[gr[x][i].first];
		}
		mx = max(mx, (int)visi.size()-sm-1);
		if(mx <= (int)visi.size()/2+1) return x;
	}

	exit(0);
	return -1;
}
int curAns[1000010];
int known[1000010];
vector<int> stt;
void dfs1(int v, int came, long long dst, int kek){
	if(dst > k) return;
	stt.push_back(dst);
	curAns[dst] = min(curAns[dst], kek);
	for(auto x : gr[v]){
		if(x.first == came) continue;
		dfs1(x.first, v, dst + x.second, kek+1);
	}
}
void jeiPrik(int v){ // suskaiciuojam, koks ats, jei v priklauso atsakymui

	known[0] = 0;
	vector<int> lik;
	for(auto x : gr[v]){
		stt.clear();
		dfs1(x.first, v, x.second, 1);
		for(auto y : stt){
		//	cout << "bandau " << y << ", tai bus galimai " << curAns[y]  << " + " << known[k-y] << endl;
			ans = min(ans, curAns[y] + known[k-y]);
		}
		for(auto y : stt){
			known[y] = min(known[y], curAns[y]);
		}
		for(auto x : stt) curAns[x] = inf;
		for(auto x : stt) lik.push_back(x);
	}
		
	for(auto x : lik){
		curAns[x] = known[x] = inf;
	}
}
void calc(int v){
	v = findCentroid(v);
	jeiPrik(v);
//	cout << "gaunam, kad centras yra " << v << endl;
	vector<int> kaims;
	for(auto x : gr[v]) kaims.push_back(x.first);
	for(auto x : visi){
		vector<pair<int, int> > naujas;
		for(auto y : gr[x]){
			if(y.first == v) continue;
			naujas.push_back(y);
		}
		gr[x] = naujas;
	}
//	cout << "istrynem " << v << endl;
	for(auto x : kaims) calc(x);
}
int best_path(int N, int K, int H[][2], int L[]){
	for(int i = 0; i <= 1000000; i++) curAns[i] = known[i] = inf;
	n = N; k = K;
	for(int i = 0; i < n-1; i++){
		gr[H[i][0]].push_back({H[i][1], L[i]});
		gr[H[i][1]].push_back({H[i][0], L[i]});
	}
	calc(0);
	return (ans == inf ? -1ll : ans);
}
/*
4 3
0 1 1
1 2 2
1 3 4
2

5 5
0 1 3
1 2 2
2 3 1
3 4 5
1
*/

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