Submission #706788

#	Time	Username	Problem	Language	Result	Execution time	Memory
706788		Asamai	Race (IOI11_race)	C++17	0 / 100	3 ms	4956 KiB

race

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
//#define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 2e5 + 5;
const int mod = 1e9 + 7; // 998244353
const int inf = 1e9 + 1;

int n, k;
vector<pii> adj[MAX_N];
bool processed[MAX_N];
int ans = inf;
int child[MAX_N];

int dfs(int u, int pr = 0) {
	child[u] = 1;
	for (auto it : adj[u]) {
		int v = it.fi;
		if (!processed[v] && v != pr) {
			child[u] += dfs(v, u);
		}
	}
	return child[u];
}

int find_centroid(int u, int pr, int sz) {
	for (auto it : adj[u]) {
		int v = it.fi;
		if (!processed[v] && v != pr && child[v] > sz) {
			return find_centroid(v, u, sz);
		}
	}
	return u;
}

const int MAX_VAL = 1e6 + 10;
int dp[MAX_VAL];
vector<int> used;

void go_cal(int u, int pr, bool ok, int len, int dep) {
	if (k < len) return;

	if (ok) {
		used.pb(len);
		minimize(dp[len], dep);
	}
	else {
		minimize(ans, dp[k - len] + dep);
	}

	for (auto it : adj[u]) {
		int v = it.fi;
		int w = it.se;
		if (!processed[v] && v != pr) {
			go_cal(v, u, ok, len + w, dep + 1);
		}
	}
}

void centroid_decomposition(int u) {
	int c = find_centroid(u, 0, dfs(u) >> 1);
	processed[c] = true;

	used.clear();

	dp[0] = 0;

	for (auto it : adj[c]) {
		int v = it.fi;
		int w = it.se;
		if (!processed[v]) {
			go_cal(v, c, false, w, 1);
			go_cal(v, c, true, w, 1);
		}
	}

	for (auto it : used) {
		dp[it] = inf;
	}

	for (auto it : adj[c]) {
		int v = it.fi;
		if (!processed[v]) {
			centroid_decomposition(v);
		}
	}
}

int best_path(int n, int k, int h[][2], int l[]) {
	for (int i = 0; i <= k; i ++) {
		dp[i] = inf;
	}
	for (int i = 0; i < n - 1; i++) {
		int u = h[i][0], v = h[i][1], w = l[i];
		u++; v++;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}

	centroid_decomposition(1);

	return (ans == inf ? -1 : ans);	
}

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