Submission #1260663

#TimeUsernameProblemLanguageResultExecution timeMemory
1260663tminhFactories (JOI14_factories)C++20
33 / 100
8096 ms264480 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]; multiset<ll> s[N]; bool del[N]; vector<pair<int, ll>> d[N]; int get_sz(int u, int p = -1) { 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 = -1) { 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].pb(make_pair(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].pb(make_pair(u, 0)); for (auto[v, w] : adj[u]) { if (del[v]) continue; make_dist(v, u, u, w); } sort(vall(d[u])); 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; ++i) par[i] = -1; 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; } ll getdist(int u, int v) { auto[node, dist] = *lower_bound(vall(d[u]), make_pair(v, 0ll)); return dist; } 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 != -1) { s[p].insert(getdist(p, u)); p = par[p]; } } ll ans = oo; for (int i = 0; i < T; ++i) { int u = Y[i]; int p = u; while(p != -1) { if (!s[p].empty()) ans = min(ans, *s[p].begin() + getdist(p, u)); p = par[p]; } } for (int i = 0; i < S; ++i) { int u = X[i]; int p = u; while(p != -1) { s[p].erase(s[p].find(getdist(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...