Submission #1260660

#TimeUsernameProblemLanguageResultExecution timeMemory
1260660tminhFactories (JOI14_factories)C++20
0 / 100
2953 ms69944 KiB
#include "bits/stdc++.h" #include "factories.h" using namespace std; #define task "" #define ll long long #define endl '\n' #define fi first #define se second #define vall(a) (a).begin(), (a).end() #define sze(a) (int)a.size() #define pii pair<int, int> #define pll pair<ll, ll> #define ep emplace_back #define pb push_back #define pf push_front const ll mod = 1e9 + 7; const int N = 5e5 + 5; const ll oo = 1e18; bool START; int n, q, par[N], sz[N]; vector<pii> adj[N]; set<ll> s[N]; bool del[N]; map<int, ll> d[N]; int get_sz(int u, int p = 0) { sz[u] = 1; for (auto[v, w] : adj[u]) { if (v == p || del[v]) continue; sz[u] += get_sz(v, u); } return sz[u]; } int get_cen(int sigma, int u, int p = 0) { for (auto[v, w] : adj[u]) { if (v != p && !del[v] && sz[v] * 2 > sigma) return get_cen(sigma, v, u); } return u; } void make_dist(int u, int p, int root, ll depth) { d[root][u] = depth; for (auto[v, w] : adj[u]) { if (v == p || del[v]) continue; make_dist(v, u, root, depth + w); } } int centroid(int u) { u = get_cen(get_sz(u), u); del[u] = true; d[u][u] = 0; for (auto[v, w] : adj[u]) { if (del[v]) continue; make_dist(v, u, u, w); } for (auto[v, w] : adj[u]) { if (del[v]) continue; int x = centroid(v); par[x] = u; } return u; } void Init(int N, int A[], int B[], int D[]){ for (int i = 0; i < N - 1; ++i) { adj[A[i]].pb(make_pair(B[i], D[i])); adj[B[i]].pb(make_pair(A[i], D[i])); } centroid(0); return; } long long Query(int S, int X[], int T, int Y[]){ for (int i = 0; i < S; ++i) { int u = X[i]; int p = u; while(p != 0) { s[p].insert(d[p][u]); p = par[p]; } } ll ans = oo; for (int i = 0; i < T; ++i) { int u = Y[i]; int p = u; while(p != 0) { if (!s[p].empty()) ans = min(ans, *s[p].begin() + d[p][u]); p = par[p]; } } for (int i = 0; i < S; ++i) { int u = X[i]; int p = u; while(p != 0) { s[p].erase(d[p][u]); p = par[p]; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...