Submission #1147954

#TimeUsernameProblemLanguageResultExecution timeMemory
1147954KodikRace (IOI11_race)C++20
100 / 100
405 ms101360 KiB
#include <bits/stdc++.h> using namespace std; #define ss second #define ff first typedef long long ll; #define ll ll using pi = array<ll, 2>; const ll MOD = 1e9+7; const int maxn = 2e5 + 1; vector<pair<int,int>> adj[maxn]; map<ll, ll> info[maxn]; ll dist[maxn], sum[maxn]; int N, K; ll ret; void precomp(int u, int p, ll c, int h) { info[u][c] = h; sum[u] = c; dist[u] = h; for (auto n : adj[u]) { if (p == n.ff) { continue; } precomp(n.ff, u, c + n.ss, h + 1); } } void small_to_large_merge(int u, int p) { ll target = K + 2 * sum[u]; for (auto n : adj[u]) { if (n.ff == p) { continue; } small_to_large_merge(n.ff, u); if (info[n.ff].size() > info[u].size()) { swap(info[n.ff], info[u]); } for (auto i : info[n.ff]) { if (info[u].find(target - i.ff) != info[u].end()) { ret = min(ret, info[u][target - i.ff] + i.ss - 2 * dist[u]); } } for (auto i : info[n.ff]) { if (info[u].find(i.ff) == info[u].end()) { info[u].insert(i); } else { info[u][i.ff] = min(info[u][i.ff], i.ss); } } } } int best_path(int n, int k, int edges[][2], int weights[]) { if (k == 1) { return 0; } N = n; K = k; ret = INT_MAX; for (int i = 0; i < n - 1; i++) { int u = edges[i][0]; int v = edges[i][1]; adj[u].push_back(pair<int,int>(v, weights[i])); adj[v].push_back(pair<int,int>(u, weights[i])); } precomp(0, -1, 0, 0); small_to_large_merge(0, -1); return ret == INT_MAX ? -1 : ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...