Submission #1260666

#TimeUsernameProblemLanguageResultExecution timeMemory
1260666tminhFactories (JOI14_factories)C++20
100 / 100
2657 ms333332 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]; bool del[N]; ll dp[N]; vector<pair<int, ll>> up[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) { up[u].pb(make_pair(root, depth)); for (auto[v, w] : adj[u]) { if (v == p || del[v]) continue; make_dist(v, u, root, depth + w); } } void centroid(int u) { u = get_cen(get_sz(u), u); del[u] = true; up[u].pb(make_pair(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; centroid(v); } } void Init(int N, int A[], int B[], int D[]){ for (int i = 0; i < N; ++i) { par[i] = -1; dp[i] = oo; } 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); for (int i = 1; i <= n; ++i) { } return; } long long Query(int S, int X[], int T, int Y[]){ for (int i = 0; i < S; ++i) { int u = X[i]; for (auto[p, depth] : up[u]) dp[p] = min(dp[p], depth); } ll ans = oo; for (int i = 0; i < T; ++i) { int u = Y[i]; for (auto[p, depth] : up[u]) ans = min(ans, dp[p] + depth); } for (int i = 0; i < S; ++i) { int u = X[i]; for (auto[p, depth] : up[u]) dp[p] = oo; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...