Submission #1084053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084053		Sunbae	Race (IOI11_race)	C++17	43 / 100	3021 ms	30032 KiB

race

#include <bits/stdc++.h>
#include "race.h"
typedef long long ll;
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
const int N = 2e5 + 5, M = 1e6 + 5, inf = 1e8;
int k, mn[M], ans = inf, sz[N];
set<int> s;
vector<pii> g[N];
bool ded[N];
void dfs(int u, int p, int d, ll w){
	if(w == k) ans = min(ans, d);
	if(w < k) ans = min(ans, d + mn[k - w]);
	for(pii it : g[u]) if(it.S != p && !ded[it.S]) dfs(it.S, u, d + 1, w + it.F);
}
void efs(int u, int p, int d, ll w){
	if(w <= k) mn[w] = min(mn[w], d), s.insert(w);
	for(pii it : g[u]) if(it.S != p && !ded[it.S]) efs(it.S, u, d + 1, w + it.F);
}
int fsz(int u, int p){
	sz[u] = 1; 
	for(pii it: g[u]) if(it.S != p && !ded[it.S]) sz[u] += fsz(it.S, u); 
	return sz[u];
}
int fcen(int u, int p, int tsz){
	for(pii it: g[u]) if(it.S != p && !ded[it.S] && sz[it.S] > tsz/2) return fcen(it.S, u, tsz);	return u;
}
void cd(int u){
	ded[u = fcen(u, -1, fsz(u, -1))] = true;
	for(pii it : g[u]) if(!ded[it.S]) dfs(it.S, u, 1, it.F), efs(it.S, u, 1, it.F);
	for(int w : s) mn[w] = inf;
	for(pii it: g[u]) if(!ded[it.S]) cd(it.S);
}
int best_path(int n, int K, int e[][2], int l[]){
	for(int i = 0; i<n; ++i) g[i].clear();
	k = K;
	for(int i = 0; i<n-1; ++i){
		int u = e[i][0], v = e[i][1], w = l[i];
		g[u].emplace_back(w, v); g[v].emplace_back(w, u);
	}
	fill(sz, sz+n, 0); fill(ded, ded+n, false); fill(mn, mn+k+1, ans = inf);
	cd(0);
	return (ans >= inf)? -1 : ans;
}
/*
signed main(){
	int n, K; scanf("%d %d", &n, &K);
	int e[n][2], l[n];
	for(int i = 0, u, v; i<n-1; ++i)	 scanf("%d %d", &e[i][0], &e[i][1]);
	for(int i = 0; i<n-1; ++i) scanf("%d", l+i);
	printf("%d\n", best_path(n, K, e, l));
}
*/

Compilation message (stderr)

race.cpp: In function 'int fcen(int, int, int)':
race.cpp:28:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   28 |  for(pii it: g[u]) if(it.S != p && !ded[it.S] && sz[it.S] > tsz/2) return fcen(it.S, u, tsz); return u;
      |  ^~~
race.cpp:28:95: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   28 |  for(pii it: g[u]) if(it.S != p && !ded[it.S] && sz[it.S] > tsz/2) return fcen(it.S, u, tsz); return u;
      |                                                                                               ^~~~~~

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