Submission #1126088

#TimeUsernameProblemLanguageResultExecution timeMemory
1126088tvgkFactories (JOI14_factories)C++20
0 / 100
8090 ms12608 KiB
#include "factories.h" #include<bits/stdc++.h> using namespace std; #define task "a" #define se second #define fi first #define ll long long #define ii pair<ll, ll> const long mxN = 5e5 + 7; int par[mxN][25], par_Cen[mxN], h[mxN], child[mxN]; bool del[mxN]; ll dis[mxN][25], mn[mxN]; vector<ii> w[mxN]; void Buildlog(int j) { for (int i = 1; i < __lg(h[j]); i++) { par[j][i] = par[par[j][i - 1]][i - 1]; dis[j][i] = dis[j][i - 1] + dis[par[j][i - 1]][i - 1]; } } void Build_LCA(int j) { Buildlog(j); for (ii i : w[j]) { if (h[i.fi]) continue; par[i.fi][0] = j; dis[i.fi][0] = i.se; h[i.fi] = h[j] + 1; Build_LCA(i.fi); } } void Pre(int j, int par) { child[j] = 1; for (ii i : w[j]) { if (del[i.fi] || i.fi == par) continue; Pre(i.fi, j); child[j] += child[i.fi]; } } int Find(int j, int sz) { for (ii i : w[j]) { if (del[i.fi] || child[i.fi] > child[j]) continue; if (child[i.fi] * 2 > sz) return Find(i.fi, sz); } return j; } const ll inf = 1e18; void Centroid(int j) { Pre(j, 0); j = Find(j, child[j]); mn[j] = inf; del[j] = 1; for (ii i : w[j]) { if (del[i.fi]) continue; par_Cen[i.fi] = j; Centroid(i.fi); } } void Init(int N, int A[], int B[], int D[]) { for (int i = 0; i < N - 1; i++) { w[A[i]].push_back({B[i], D[i]}); w[B[i]].push_back({A[i], D[i]}); } h[1] = 1; Build_LCA(1); Centroid(1); } ll LCA(int u, int v) { if (h[u] < h[v]) swap(u, v); ll res = 0; for (int i = 19; i >= 0; i--) { if (h[u] - (1 << i) >= h[v]) { res += dis[u][i]; u = par[u][i]; } } if (u == v) return res; for (int i = 19; i >= 0; i--) { if (par[u][i] != par[v][i]) { res += dis[u][i] + dis[v][i]; u = par[u][i]; v = par[v][i]; } } return res + dis[u][0] + dis[v][0]; } long long Query(int S, int X[], int T, int Y[]) { vector<int> ver; for (int i = 0; i < S; i++) { int cur = X[i]; while (cur) { ver.push_back(cur); mn[cur] = min(mn[cur], LCA(X[i], cur)); cur = par_Cen[cur]; } } ll ans = inf; for (int i = 0; i < T; i++) { int cur = Y[i]; while (cur) { ans = min(ans, mn[cur] + LCA(Y[i], cur)); cur = par_Cen[cur]; } } for (int i : ver) mn[i] = inf; return ans; } // //#include <stdlib.h> // //#define MAX_N 500000 //#define MAX_Q 100000 //#define MAX_SUM_ST 1000000 //#define MAX_VALUE 1000000000 // //static int N, Q; //static int A[MAX_N], B[MAX_N], D[MAX_N]; //static int S[MAX_N]; //static int T[MAX_N]; //static int X[MAX_SUM_ST]; //static int Y[MAX_SUM_ST]; // //static int Qx[MAX_N]; //static int Qy[MAX_N]; // //int main() { // freopen("sample-in-01.txt","r",stdin); // // int i, j, k; // int STop, TTop; // // if (2 != scanf("%d%d", &N, &Q)) { // fprintf(stderr, "error: cannot read N and Q.\n"); // exit(1); // } // if (!(2 <= N && N <= MAX_N)) { // fprintf(stderr, "error: N is out of bounds.\n"); // exit(1); // } // if (!(1 <= Q && Q <= MAX_Q)) { // fprintf(stderr, "error: Q is out of bounds.\n"); // exit(1); // } // for (i = 0; i < N - 1; ++i) { // if (1 != scanf("%d", &A[i])) { // fprintf(stderr, "error: cannot read A[%d].\n", i); // exit(1); // } // if (!(0 <= A[i] && A[i] <= N - 1)) { // fprintf(stderr, "error: A[%d] is out of bounds.\n", i); // exit(1); // } // if (1 != scanf("%d", &B[i])) { // fprintf(stderr, "error: cannot read B[%d].\n", i); // exit(1); // } // if (!(0 <= B[i] && B[i] <= N - 1)) { // fprintf(stderr, "error: B[%d] is out of bounds.\n", i); // exit(1); // } // if (A[i] == B[i]) { // fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i); // exit(1); // } // if (1 != scanf("%d", &D[i])) { // fprintf(stderr, "error: cannot read D[%d].\n", i); // exit(1); // } // if (!(1 <= D[i] && D[i] <= MAX_VALUE)) { // fprintf(stderr, "error: D[%d] is out of bounds.\n", i); // exit(1); // } // } // // STop = 0; // TTop = 0; // // for (j = 0; j < Q; ++j) { // if (2 != scanf("%d%d", &S[j], &T[j])) { // fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j); // exit(1); // } // // if(STop + S[j] > MAX_SUM_ST) { // fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j); // exit(1); // } // // if(TTop + T[j] > MAX_SUM_ST) { // fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j); // exit(1); // } // // for (k = 0; k < S[j]; ++k, ++STop) { // if (1 != scanf("%d", &X[STop])) { // fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k); // exit(1); // } // // if (!(0 <= X[STop] && X[STop] <= N - 1)) { // fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k); // exit(1); // } // } // // for (k = 0; k < T[j]; ++k, ++TTop) { // if (1 != scanf("%d", &Y[TTop])) { // fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k); // exit(1); // } // // if (!(0 <= Y[TTop] && Y[TTop] <= N - 1)) { // fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k); // exit(1); // } // } // } // // STop = 0; // TTop = 0; // Init(N, A, B, D); // // for (j = 0; j < Q; ++j) { // for (k = 0; k < S[j]; k++) { // Qx[k] = X[STop++]; // } // for (k = 0; k < T[j]; k++) { // Qy[k] = Y[TTop++]; // } // // printf("%lld\n", Query(S[j], Qx, T[j], Qy)); // } // // // return 0; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...