Submission #798760

#TimeUsernameProblemLanguageResultExecution timeMemory
798760OrazBFactories (JOI14_factories)C++14
18 / 100
8044 ms145012 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; #define all(x) (x).begin(), (x).end() #define ll long long int #define pii pair <int, ll> #define pb push_back #define ff first #define ss second const int N = 5e5+5; const ll inf = 1e18; int rem[N], sub[N], par[N], sp[N][20], lvl[N]; ll w[N], cur[N]; vector<pii> E[N]; // void dfs(int nd, int pr){ // sub[nd] = 1; // for (auto i : E[nd]){ // if (i.ff == pr or rem[i.ff]) continue; // dfs(i.ff, nd); // sub[nd] += sub[i.ff]; // } // } // int centroid(int nd, int pr, int sz){ // for (auto i : E[nd]){ // if (i.ff == pr or rem[i.ff]) continue; // if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz); // } // return nd; // } // void build(int nd, int pr){ // int centr = centroid(nd, 0, sub[nd]); // rem[centr] = 1; // par[centr] = pr; // for (auto i : E[centr]){ // if (!rem[i.ff]){ // dfs(i.ff, 0); // build(i.ff, centr); // } // } // } void dfs2(int nd, int pr){ sp[nd][0] = pr; for (auto i : E[nd]){ if (i.ff == pr) continue; lvl[i.ff] = lvl[nd]+1; w[i.ff] = w[nd]+i.ss; dfs2(i.ff, nd); } } int LCA(int u, int v){ if (lvl[u] < lvl[v]) swap(u, v); int diff = lvl[u]-lvl[v]; for (int i = 19; i >= 0; i--){ if (diff&(1<<i)) u = sp[u][i]; } if (u == v) return v; for (int i = 19; i >= 0; i--){ if (sp[u][i] != sp[v][i]){ u = sp[u][i]; v = sp[v][i]; } } return sp[u][0]; } ll dist(int u, int v){ if (u == v) return 0ll; return w[u]+w[v]-2*w[LCA(u,v)]; } void Init(int n, int A[], int B[], int D[]){ for (int i = 0; i < n-1; i++){ A[i]++; B[i]++; E[A[i]].pb({B[i], D[i]}); E[B[i]].pb({A[i], D[i]}); } // dfs(1, 0); // build(1, 0); dfs2(1, 0); for (int j = 1; j <= 19; j++){ for (int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j-1]][j-1]; } for (int i = 1; i <= n; i++) cur[i] = inf; } // void remv(int nd){ // while(nd){ // cur[nd] = inf; // nd = par[nd]; // } // } // void paint(int nd){ // int u = nd; // while(u){ // cur[u] = min(cur[u], dist(u, nd)); // u = par[u]; // } // } // ll find(int nd){ // ll mn = inf; // int u = nd; // while(u){ // mn = min(mn, dist(u, nd)+cur[u]); // u = par[u]; // } // return mn; // } ll Query(int S, int X[], int T, int Y[]){ for (int i = 0; i < S; i++){ X[i]++; // paint(X[i]); } ll ans = inf; for (int i = 0; i < T; i++){ Y[i]++; // ans = min(ans, find(Y[i])); for (int j = 0; j < S; j++){ ans = min(ans, dist(X[j], Y[i])); } } // for (int i = 0; i < S; i++) remv(X[i]); return ans; } // int main () // { // int n, q; // cin >> n >> q; // int A[n], B[n], D[n]; // for (int i = 0; i < n-1; i++){ // cin >> A[i] >> B[i] >> D[i]; // } // Init(n, A, B, D); // for (int i = 0; i < q; i++){ // int S, T; // cin >> S >> T; // int X[S], Y[T]; // for (int j = 0; j < S; j++) cin >> X[j]; // for (int j = 0; j < T; j++) cin >> Y[j]; // cout << Query(S, X, T, Y) << '\n'; // } // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...