Submission #44735

#TimeUsernameProblemLanguageResultExecution timeMemory
44735PowerOfNinjaGoFactories (JOI14_factories)C++11
15 / 100
6056 ms123552 KiB
//Power Of Ninja Go #include <bits/stdc++.h> #ifdef atom #include "grader.cpp" #else #include "factories.h" #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii; #define X first #define Y second #define pb push_back const int maxn = 5e5+5; vii adj[maxn]; int dp[22][maxn]; int h[maxn]; int par[maxn]; ll sweep[maxn]; int cnt[maxn]; bool use[maxn]; ll bst[maxn]; void trv(int u, int p) { for(auto edge : adj[u]) { int v = edge.X, w = edge.Y; if(v != p) { h[v] = h[u]+1; dp[0][v] = u; sweep[v] = sweep[u]+w; trv(v, u); } } } void dfs(int u, int p) { cnt[u] = 1; for(auto edge : adj[u]) { int v = edge.X; if(use[v] or v == p) continue; dfs(v, u); cnt[u] += cnt[v]; } } int find_centroid(int u, int p, int full) { for(auto edge : adj[u]) { int v = edge.X; if(use[v] or v == p) continue; if(cnt[v]*2> full) return find_centroid(v, u, full); } return u; } void maketree(int top, int p) { dfs(top, p); int c = find_centroid(top, p, cnt[top]); use[c] = true; par[c] = p; //printf("centroid %d\n", c); for(auto edge : adj[c]) { int v = edge.X; if(use[v] or v == p) continue; maketree(v, c); } } int LCA(int u, int v) { if(h[u]< h[v]) swap(u, v); for(int i = 20; i>= 0; i--) { int x = dp[i][u]; if(h[x]>= h[v]) u = x; } if(u == v) return u; for(int i = 20; i>= 0; i--) { int x = dp[i][u], y = dp[i][v]; if(x == y) continue; u = x; v = y; } return dp[0][u]; } ll dist(int u, int v) { int x = LCA(u, v); return sweep[u]+sweep[v]-2LL*sweep[x]; } void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i< N-1; i++) { int u, v; u = A[i]+1; v = B[i]+1; int w = D[i]; adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w)); } h[1] = 1; trv(1, 0); //for(int i = 1; i<= N; i++) printf("sweep[i] = %lld\n", sweep[i]); maketree(1, 0); for(int i = 1; i<= 20; i++) for(int j = 1; j<= N; j++) dp[i][j] = dp[i-1][dp[i-1][j]]; for(int i = 1; i<= N; i++) bst[i] = 4e18; } long long Query(int S, int X[], int T, int Y[]) { vector<int> vec; for(int i = 0; i< S; i++) { int u = X[i]+1; //printf("updating %d\n", u); while(u) { bst[u] = min(bst[u], dist(u, X[i]+1)); //printf("bst[%d] is now %lld\n", u, bst[u]); vec.pb(u); u = par[u]; } } ll best = 4e18; for(int i = 0; i< T; i++) { int u = Y[i]+1; int len = 0; while(u) { best = min(best, dist(u, Y[i]+1)+bst[u]); u = par[u]; len++; } } for(auto x : vec) bst[x] = 4e18; return best; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...