Submission #711924

#	Time	Username	Problem	Language	Result	Execution time	Memory
711924		Hoff22	경주 (Race) (IOI11_race)	C++17	9 / 100	217 ms	43652 KiB

race

#include "race.h"
#include <bits/stdc++.h>
 
#define N 200000
#define MAX 1000000000
#define E 0.00000001
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFll 0x3f3f3f3f3f3f3f3fll
#define LEFT(x) (2 * x)
#define RIGHT(x) (2 * x + 1)
#define se second
#define fi first
 
using namespace std;
 
typedef long long ll;
 
vector<int> g[N+1];
map<pair<int,int>, ll> e;
map<ll,int> d[N+1];
ll dist[N+1];
int sz[N+1];
int ans = -1;
 
void prec(ll u, ll p){
	dist[u] = dist[p] + e[{u,p}];
	for(ll v : g[u]){
		if(v == p) continue;
		prec(v, u);
	}
}
 
void solve(int u, int p, int depth, ll k){
	
	int big = -1;
	sz[u] = 1;
	
	for(int v : g[u]){
		if(v == p) continue;
		solve(v, u, depth+1, k);
		sz[u] += sz[v];
		if(big == -1 or sz[v] > sz[big]) big = v;
	}
 
	if(big == -1){
		d[u][dist[u]] = depth;	
		return;
	}
 
	swap(d[u], d[big]);
 
	d[u][dist[u]] = depth;
 
	if(d[u].count(k + dist[u])){
		if(ans == -1) ans = d[u][k + dist[u]] - depth;
		else  ans = min(ans, d[u][k + dist[u]] - depth);
	}
 
	for(int v : g[u]){
		if(v == p or v == big) continue; 
		for(auto i : d[v]){
			// if(d[u].count(i.fi)){
			// 	d[u][i.fi] = min(d[u][i.fi], i.se);
			// }
			// else{
			// 	d[u][i.fi] = i.se;
			// }
			d[u][i.fi] = i.se;
			ll want = k + 2 * dist[u] - i.fi;
			if(d[u].count(want)){
				if(ans == -1) ans = (d[u][i.fi] - depth) + (d[u][want] - depth); 
				else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
			}
 
		}
	}

	if(d[u].count(k + dist[u])){
		if(ans == -1) ans = d[u][k + dist[u]] - depth;
		else  ans = min(ans, d[u][k + dist[u]] - depth);
	}
}
 
int best_path(int n, int k, int (*h)[2], int* l){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	for(ll i = 0; i <= n; i++){
		g[i].clear();
		dist[i] = 0;
		sz[i] = 0;
		d[i].clear();
	}
	ans = -1;
	e.clear();
 
	for(ll i = 0; i < n-1; i++){
		ll u, v, w;
		u = h[i][0];
		v = h[i][1];
		w = l[i];
 
		u++;
		v++;
 
		g[u].push_back(v);
		g[v].push_back(u);
		e[{u,v}] = w;
		e[{v,u}] = w;
	}
 
	prec(1,0);
	solve(1, 0, 0, k);
 
	return ans;
}

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