Submission #1022552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022552		socpite	Race (IOI11_race)	C++14	0 / 100	2 ms	10584 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5+5;

map<long long, int> mp;

int sz[maxn];
int dep1[maxn];
long long dep2[maxn];
vector<pair<int, int>> g[maxn];

void add(long long val, int dep){
	if(mp.find(val) != mp.end())mp[val] = min(mp[val], dep);
	else mp[val] = dep;
}

int query(long long val){
	if(mp.find(val) == mp.end())return maxn;
	else return mp[val];
}

// k = dep[a] + dep[b] - 2*dep[lca] => dep[b] = k - dep[a] + 2*dep[lca];

void pre_dfs(int x, int p){
	sz[x] = 1;
	for(auto v: g[x]){
		if(v.first == p)continue;
		dep1[v.first] = dep1[x] + 1;
		dep2[v.first] = dep2[x] + v.second;
		pre_dfs(v.first, x);
		sz[x] += sz[v.first];
	}
}

int dfs_query(int x, int p, long long coeff){
	int re = query(coeff - dep2[x]) + dep1[x];
	for(auto v: g[x]){
		if(v.first == p)continue;
		re = min(re, dfs_query(v.first, x, coeff));
	}
	return re;
}

void dfs_add(int x, int p){
	add(dep2[x], dep1[x]);
	for(auto v: g[x]){
		if(v.first == p)continue;
		dfs_add(v.first, x);
	}
}

int dfs(int x, int p, int k){
	sz[x] = 1;
	int ans = maxn, bg = -1;
	for(auto v: g[x]){
		if(v.first == p)continue;
		if(bg == -1 || sz[bg] < sz[v.first])bg = v.first;
	}
	for(auto v: g[x]){
		if(v.first == p || v.first == bg)continue;
		ans = min(ans, dfs(v.first, x, k));
		mp.clear();
	}
	if(bg != -1)dfs(bg, x, k);
	for(auto v: g[x]){
		if(v.first == p || v.first == bg)continue;
		ans = min(ans, dfs_query(v.first, x, 2*dep2[x] + k) - 2*dep1[x]);
		dfs_add(v.first, x);
	}
	ans = min(ans, query(dep2[x] + k) - dep1[x]);
	add(dep2[x], dep1[x]);
	return ans;
}


int best_path(int N, int K, int H[][2], int L[])
{
	dep1[0] = 0;
	dep2[0] = 0;
	for(int i = 0; i < N; i++)g[i].clear();
	for(int i = 0; i < N-1; i++){
		g[H[i][0]].push_back({H[i][1], L[i]});
		g[H[i][1]].push_back({H[i][0], L[i]});
	}
	pre_dfs(0, -1);
	int ans = dfs(0, -1, K);
	return ans == maxn ? -1 : ans;
}

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