Submission #58777

#	Time	Username	Problem	Language	Result	Execution time	Memory
58777		Sherazin	Race (IOI11_race)	C++14	0 / 100	7 ms	5244 KiB

race

//#include "race.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 5;

int n, k;
int ans = -1, centroid, mxnode, all, cnt;
int dep[N], path[N], dp[N];
vector<vector<pii> > g(N);
bitset<N> chk;

int subtree(int u, int p) {
	for(pii v : g[u]) if(!chk[v.x] && v.x != p) {
		dep[u] += subtree(v.x, u);
	}
	return ++dep[u];
}

void centdecomp(int u, int p) {
	int ret = all - dep[u];
	for(pii v : g[u]) if(!chk[v.x] && v.x != p) {
		centdecomp(v.x, u);
		ret = max(ret, dep[v.x]);
	}
	if(ret < mxnode) centroid = u, mxnode = ret;
}

void dfs(int u, int p, int cost, int edge, bool fill) {
	if(cost > k) return;
	if(!fill) {
		if(dp[k - cost] == cnt && (ans == -1 || edge + path[k - cost] < ans)) ans = edge + path[k - cost];
		if(cost = k && (ans == -1 || edge < ans)) ans = edge;
	} else {
		if(dp[cost] < cnt) dp[cost] = cnt, path[cost] = edge;
		else if(edge < path[cost]) dp[cost] = cnt, path[cost] = edge;
	}

	for(pii v : g[u]) if(!chk[v.x] && v.x != p) {
		dfs(v.x, u, cost + v.y, edge + 1, fill);
	}
}

void proc(int u) {
	cnt++;
	if(subtree(u, u) <= 1) return;
	centroid = -1;
	mxnode = dep[u];
	all = dep[u];
	centdecomp(u, u);
	for(pii v : g[centroid]) if(!chk[v.x]) {
		dfs(v.x, centroid, v.y, 1, false);
		dfs(v.x, centroid, v.y, 1, true);
	}
	chk[centroid] = 1;
	for(pii v : g[centroid]) if(!chk[v.x]) {
		proc(v.x);
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K;
	for(int i = 0; i < N - 1; i++) {
		g[H[i][0]].emplace_back(H[i][1], L[i]);
		g[H[i][1]].emplace_back(H[i][0], L[i]);
	}

	proc(0);

	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int, int, bool)':
race.cpp:38:11: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(cost = k && (ans == -1 || edge < ans)) ans = edge;
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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