Submission #71491

#	Time	Username	Problem	Language	Result	Execution time	Memory
71491		RezwanArefin01	Race (IOI11_race)	C++17	100 / 100	2109 ms	114532 KiB

race

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

typedef long long ll;
typedef pair<int, int> ii; 

const int maxn = 2e5 + 10; 
vector<int> adj[maxn], cost[maxn]; 
ll dist[maxn]; bool vis[maxn]; 
int sub[maxn], len[maxn], n, k; 
int ans = 1e9; 

void calc(int u, int par) {
	sub[u] = 1;
	for(int v : adj[u]) if(v - par && !vis[v]) 
		calc(v, u), sub[u] += sub[v];
}

int centroid(int u, int par, int r) {
	for(int v : adj[u]) if(v - par && !vis[v]) 
		if(sub[v] > r) return centroid(v, u, r);
	return u;
}

vector<int> vert; int in[maxn], out[maxn];

void dfs(int u, int par) { 
	in[u] = vert.size(); vert.push_back(u);
	for(int i = 0; i < adj[u].size(); ++i) {
		int v = adj[u][i], c = cost[u][i];
		if(v == par || vis[v]) continue; 
		dist[v] = dist[u] + c; 
		len[v] = len[u] + 1;
		dfs(v, u); 
	} out[u] = vert.size() - 1;
}
void solve(int u) {
	dist[u] = len[u] = 0;
	vert.clear(); dfs(u, -1);

	unordered_map<ll, int> mp; mp[0] = 0;

	for(int v : adj[u]) if(!vis[v]) {
		for(int t = in[v]; t <= out[v]; ++t) {
			int w = vert[t];
			if(mp.count(k - dist[w])) 
				ans = min(ans, mp[k - dist[w]] + len[w]); 
		}
		for(int t = in[v]; t <= out[v]; ++t) {
			int w = vert[t];
			if(!mp.count(dist[w])) mp[dist[w]] = len[w];
			else mp[dist[w]] = min(mp[dist[w]], len[w]);
		}
	}

}
void decomp(int u, int par) {
	calc(u, -1); 
	int c = centroid(u, par, sub[u] / 2);
	solve(c); vis[c] = 1; 
	for(int v : adj[c]) if(!vis[v]) decomp(v, c);
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N, k = K; 
	for(int i = 0; i < N - 1; i++) {
		adj[H[i][0]].push_back(H[i][1]); 
		adj[H[i][1]].push_back(H[i][0]); 
		cost[H[i][0]].push_back(L[i]);
		cost[H[i][1]].push_back(L[i]);
	}
	decomp(0, -1);	
	if(ans == 1e9) ans = -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~

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