Submission #833820

#	Time	Username	Problem	Language	Result	Execution time	Memory
833820		MODDI	Race (IOI11_race)	C++14	100 / 100	1295 ms	46232 KiB

race

#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
vector<pii> G[200100];
vi sz, vis;
map<int, int> mapa;
int ans = 1e8, req_len;
int dfs_sz(int node, int p){
	sz[node] = 1;
	for(auto next : G[node]){
		if(next.first != p && !vis[next.first]){
			sz[node] += dfs_sz(next.first, node);
		}
	}
	return sz[node];
}
int find_centroid(int node, int p, int n){
	for(auto next : G[node]){
		if(next.first != p && !vis[next.first] && sz[next.first] * 2 >= n)
			return find_centroid(next.first, node, n);
	}
	return node;
}
void proveri(int node, int p, int dist, int cnt){
	if(dist > req_len)	return;
	if(req_len - dist == 0){
		ans = min(ans, cnt);
	}
	else if(req_len - dist != 0 && mapa[req_len - dist] != 0){
		ans = min(ans, mapa[req_len - dist] + cnt);
	}
	for(auto next : G[node]){
		if(next.first != p && !vis[next.first])
			proveri(next.first, node, dist + next.second, cnt + 1);
	}
}
void dodadi(int node, int p, int dist, int cnt){
	if(dist > req_len)	return ;
	if(mapa[dist] == 0)	mapa[dist] = cnt;
	else
		mapa[dist] = min(mapa[dist], cnt);
		
	for(auto next : G[node]){
		if(next.first != p && !vis[next.first])
			dodadi(next.first, node, dist + next.second, cnt + 1);
	}
}
void recur(int node, int p){
	int n = dfs_sz(node, p);
	int centroid = find_centroid(node, p, n);
	vis[centroid] = true;
	mapa = map<int,int>();
	for(auto next : G[centroid]){
		if(!vis[next.first]){
			proveri(next.first, centroid, next.second, 1);
			dodadi(next.first, centroid, next.second, 1);
		}	
	}
	for(auto next : G[centroid]){
		if(next.first != p && !vis[next.first]){
			recur(next.first, centroid);
		}
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	req_len = K;
	sz = vi(N);
	vis = vi(N, false);
	for(int i = 0; i < N-1; i++){
		G[H[i][0]].pb(mp(H[i][1], L[i]));
		G[H[i][1]].pb(mp(H[i][0], L[i]));
	}
	recur(0, 0);
	if(ans >= 1e8)	return -1;
	return ans;
}

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