Submission #29229

#TimeUsernameProblemLanguageResultExecution timeMemory
29229ruhanhabib39Factories (JOI14_factories)C++14
33 / 100
6000 ms212464 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 5e5; const int MAXLG = 20; const long long INF = 1e18; int N; vector<pair<int,int>> G[MAXN + 10]; int cc[MAXN + 10]; int level[MAXN + 10]; long long dis[MAXLG + 10][MAXN + 10]; bool done[MAXN + 10]; int par[MAXN + 10]; void dfs(int u, int p, long long ds) { dis[++level[u]][u] = ds; cc[u] = 1; for(auto e : G[u]) { int v, d; tie(v, d) = e; if(v == p || done[v]) continue; dfs(v, u, ds + d); cc[u] += cc[v]; } } int centroid(int u, int p, int cnt) { for(auto e : G[u]) { int v = e.first; if(v == p || done[v]) continue; if(cc[v] > cnt/2) return centroid(v, u, cnt); } return u; } void decomp(int u, int p) { u = centroid(u, -1, cc[u]); dfs(u, -1, 0); // cerr << "centroid = " << u << "\n"; par[u] = p; done[u] = true; for(auto e : G[u]) { int v = e.first; if(done[v]) continue; decomp(v, u); } } long long mn[MAXN + 10]; void Init(int N_, int A[], int B[], int D[]) { N = N_; for(int i = 0; i < N-1; i++) { G[A[i]].emplace_back(B[i], D[i]); G[B[i]].emplace_back(A[i], D[i]); } memset(level, -1, sizeof(level)); dfs(0, -1, 0); decomp(0, -1); std::fill(mn, mn + MAXN + 1, INF); } long long Query(int S, int X[], int T, int Y[]) { // cerr << "\n\n"; for(int i = 0; i < S; i++) { int u = X[i]; // cerr << "Xu = " << u << "\n"; for(int j = level[u]; j > 0; j--) { mn[u] = min(mn[u], dis[j][X[i]]); // cerr << "mn[" << u << "] = " << mn[u] << "\n"; u = par[u]; } } long long res = INF; for(int i = 0; i < T; i++) { int u = Y[i]; for(int j = level[u]; j > 0; j--) { res = min(res, mn[u] + dis[j][Y[i]]); u = par[u]; } } for(int i = 0; i < S; i++) { int u = X[i]; for(int j = level[u]; j > 0; j--) { mn[u] = INF; u = par[u]; } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...