제출 #706788

#제출 시각아이디문제언어결과실행 시간메모리
706788Asamai경주 (Race) (IOI11_race)C++17
0 / 100
3 ms4956 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...