Submission #585970

#	Time	Username	Problem	Language	Result	Execution time	Memory
585970		M_W	Race (IOI11_race)	C++17	0 / 100	60 ms	12836 KiB

race

#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int bk[1000002], mn[1000002];
bool blocked[200001];
vector<ii> adj[200001];
int sz[200001], book = 1;
int ans = 1e9, K;

// Centroid

void dfs(int a, int p){
	sz[a] = 1;
	for(auto [x, w] : adj[a]){
		if(blocked[x] || x == p) continue;
		dfs(x, a);
		sz[a] += sz[x];
	}
}

void dfs_upd(int a, int p, long long wt, int ed){
	for(auto [x, w] : adj[a]){
		if(blocked[x] || x == p) continue;
		
		int idx = int(min(1000001 * 1ll, wt + w));
		bk[idx] = book; mn[idx] = mn[idx] == 0 ? ed : min(mn[idx], ed);
		dfs_upd(x, a, wt + w, ed + 1);
	}
}

void dfs_path(int a, int p, long long wt, int ed){
	for(auto [x, w] : adj[a]){
		if(blocked[x] || x == p) continue;
		
		int idx = int(min(1000001 * 1ll, wt + w));
		if(K - idx >= 0){
			if(bk[K - idx] < book && bk[K - idx]) ans = min(ans, ed + mn[K - idx]);
		}
		dfs_path(x, a, wt + w, ed + 1);
		
		
		if(ed == 1){
			bk[idx] = book; mn[idx] = mn[idx] == 0 ? ed : min(mn[idx], ed);
			dfs_upd(x, a, wt + w, ed + 1);
		} 
		
		book++;
	}
}

void dec(int a, int p){
	dfs(a, a);
	int cur = a, prev = -1;
	while(true){
		int mx = -1, nxt;
		for(auto [x, w] : adj[cur]){
			if(blocked[x] || x == prev) continue;
			if(sz[x] > mx){
				mx = sz[x];
				nxt = x;
			}
		}
		if(mx * 2 > sz[a]){
			prev = cur;
			cur = nxt;
		}
		else break;
	}
	blocked[cur] = true;
	book = 1;
	dfs_path(cur, cur, 0, 1);
	
	memset(bk, 0, sizeof bk);
	memset(mn, 0, sizeof mn);
	for(auto [x, w]: adj[cur]) if(!blocked[x]) dec(x, cur);
}

int best_path(int N, int K_tmp, int H[][2], int L[])
{
	K = K_tmp;
	for(int i = 0; i < N - 1; i++){
		adj[H[i][0]].push_back({H[i][1], L[i] * 1ll});
		adj[H[i][1]].push_back({H[i][0], L[i] * 1ll});
	}
	dec(0, -1);
	return ans == 1000000000 ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In function 'void dec(int, int)':
race.cpp:55:16: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   int mx = -1, nxt;
      |                ^~~

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