Submission #86980

#TimeUsernameProblemLanguageResultExecution timeMemory
86980wzyFactories (JOI14_factories)C++11
33 / 100
5796 ms525312 KiB
#include <bits/stdc++.h> #include"factories.h" using namespace std; #define ll long long const int N = 500005; vector< array<int, 2 > > adj[N]; int paiC[N]; bool blocked[N]; int sz[N]; ll vl[N]; ll maxint = 1000000000000000000ll; int n; ll dist[N][22]; int layer[N]; void computa(int x , int y){ sz[x] = 1; for(auto w : adj[x]){ if(blocked[w[0]] || y == w[0]) continue; computa(w[0] , x); sz[x] += sz[w[0]]; } } int find_C(int x , int y , int root){ int centroid = x; for(auto w : adj[x]){ if(blocked[w[0]] || y == w[0]) continue; if(sz[w[0]] > sz[root]/2) centroid = find_C(w[0] , x , root); } return centroid; } void fill_dp(int x , int y , int pai , int root , ll dis){ dist[x][layer[root]] = dis; for(auto w : adj[x]){ if(blocked[w[0]] || y == w[0]) continue; fill_dp(w[0] , x , pai, root ,(ll)dis + 1ll*w[1]); } } void decompose(int x = 0, int pai = -1){ computa(x , x); x = find_C(x , x , x); paiC[x] = pai; if(pai == -1) layer[x] = 0; else layer[x] = layer[pai] + 1; fill_dp(x , x , pai , x,0); blocked[x] = true; for(auto w : adj[x]){ if(!blocked[w[0]]) decompose(w[0] , x); } } void Init(int N, int A[], int B[], int D[]){ for(int i = 0 ; i < N - 1 ; i ++){ adj[A[i]].push_back({B[i] , D[i]}); adj[B[i]].push_back({A[i] , D[i]}); } n = N; decompose(); for(int i = 0 ; i < N ; i ++){ vl[i] = maxint; } } long long Query(int S, int X[], int T, int Y[]){ for(int i = 0 ; i < S ; i ++){ ll currdis = 0; int x = X[i]; while(x != -1){ vl[x] = min(vl[x] , dist[X[i]][layer[x]]); x = paiC[x]; } } ll ans = maxint; for(int i = 0 ; i < T ; i ++){ ll currdis = 0; int x = Y[i]; while(x != -1){ ans = min(ans , dist[Y[i]][layer[x]] + vl[x]); x = paiC[x]; } } for(int i = 0 ; i < S ; i ++){ int x = X[i]; while(x != -1){ vl[x] = maxint; x = paiC[x]; } } return ans; }

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:76:6: warning: unused variable 'currdis' [-Wunused-variable]
   ll currdis = 0;
      ^~~~~~~
factories.cpp:85:6: warning: unused variable 'currdis' [-Wunused-variable]
   ll currdis = 0;
      ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...