제출 #111059

#제출 시각아이디문제언어결과실행 시간메모리
111059Plasmatic공장들 (JOI14_factories)C++11
0 / 100
8087 ms130436 KiB
//============================================================================ // Name : joi14p1.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include "factories.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; // Scan and Debug void scan(){} template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);} int di_; string dnms_, co_ = ","; void debug_(){cout<<endl;} template<typename F, typename... R> void debug_(F f, R... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);} #define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__) const int MAX = 500001, ESZ = 1000001; constexpr int LOG = log2(ESZ) + 1; struct ed { int v, w; }; vector<ed> matrix[MAX]; const ll INF = 0x3f3f3f3f3f3f3f3f; int N, sz[MAX], par[MAX], lv[MAX]; bool blocked[MAX]; ll bestFor[MAX]; vector<int> back; vector<ll> dis[MAX]; int gsz(int cur, int par) { sz[cur] = 1; for (ed adj : matrix[cur]) if ((adj.v ^ par) && !blocked[adj.v]) sz[cur] += gsz(adj.v, cur); return sz[cur]; } int gcentroid(int cur, int par, int half) { for (ed adj : matrix[cur]) if ((adj.v ^ par) && !blocked[adj.v] && sz[adj.v] > half) return gcentroid(adj.v, cur, half); return cur; } void dfs(int cur, int par=-1, ll __dis=0) { dis[cur].push_back(__dis); for (ed adj : matrix[cur]) if ((adj.v ^ par) && !blocked[adj.v]) dfs(adj.v, cur, __dis + adj.w); } int decomp(int cur=0, int __par=-1, int __lv=0) { gsz(cur, __par); if (sz[cur] == 1) {// If size is one, centroid is self lv[cur] = __lv; return cur; } int centroid = gcentroid(cur, __par, sz[cur] >> 1); lv[centroid] = __lv; blocked[centroid] = true; dfs(centroid); for (ed adj : matrix[centroid]) if (!blocked[adj.v]) par[decomp(adj.v, centroid, __lv + 1)] = centroid; return centroid; } // Grader Functions void Init(int N_, int A[], int B[], int D[]) { N = N_; for (int i = 0; i < N - 1; i++) { matrix[A[i]].push_back({B[i], D[i]}); matrix[B[i]].push_back({A[i], D[i]}); } // Init Centroid Tree par[decomp()] = -1; memset(bestFor, 0x3f, sizeof bestFor); } long long Query(int S, int X[], int T, int Y[]) { ll best = INF; for (int i = 0; i < T; i++) { for (int cur = Y[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--) { bestFor[cur] = min(bestFor[cur], dis[Y[i]][clv]); back.push_back(cur); } } for (int i = 0; i < S; i++) for (int cur = X[i], clv = lv[cur]; cur != -1; cur = par[cur], clv--) best = min(best, dis[X[i]][clv] + bestFor[cur]); for (int x : back) bestFor[x] = INF; return best; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...