제출 #90857

#제출 시각아이디문제언어결과실행 시간메모리
90857liwi공장들 (JOI14_factories)C++11
0 / 100
8069 ms12408 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0) char _; #define println printf("\n"); #define readln(x) getline(cin,x); #define pb push_back #define endl "\n" #define MOD 1000000007 #define mp make_pair #define MAXN 500005 #define LOGN 25 typedef unsigned long long ull; typedef long long ll; typedef long double ld; typedef unordered_map<int,int> umii; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,pii> triple; typedef int8_t byte; ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);} ll fpow(ll b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;} ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;} int num_nodes,num_q,sz[MAXN],lvl[MAXN],par[MAXN],upd[MAXN],qcnt,A[MAXN],B[MAXN],D[MAXN],cur_lvl; ll small[MAXN],dis[LOGN][MAXN]; bool done[MAXN]; vector<pii> tconnections[MAXN]; int getSz(int node, int prev, ll dd){ sz[node] = 1; dis[cur_lvl][node] = dd; for(pii check:tconnections[node]){ if(check.first == prev || done[check.first]) continue; sz[node]+=getSz(check.first,node,dd+check.second); } return sz[node]; } int centroid(int u, int p, int psz, pii &ret) { sz[u] = 1; int mxsz = 0; for(auto v : tconnections[u]) if(v.first != p and !done[v.first]) { int now = centroid(v.first, u, psz, ret); mxsz = max(mxsz, now); sz[u] += now; } mxsz = max(mxsz, psz - sz[u]); if(mxsz < ret.first) ret = pii(mxsz, u); return sz[u]; } void getTree(int node, int prev, int mx, int lv){ cur_lvl = lv; pii ret = mp(mx,-1); centroid(node,-1,mx,ret); node = ret.second; par[node] = prev, lvl[node] = lv, done[node] = true; getSz(node,-1,0); for(pii check:tconnections[node]){ if(check.first == prev || done[check.first]) continue; getTree(check.first,node,sz[check.first],lv+1); } } void Init(int N, int A[MAXN], int B[MAXN], int D[MAXN]){ for(int i=0; i<N-1; i++){ int a = A[i], b = B[i], dis = D[i]; tconnections[a].pb(mp(b,dis)); tconnections[b].pb(mp(a,dis)); } getTree(0,-1,num_nodes,0); } ll Query(int s1, int X[MAXN], int s2, int Y[MAXN]){ ++qcnt; for(int i=0; i<s1; i++){ int current = X[i]; while(current != -1){ if(upd[current] == qcnt) small[current] = min(small[current],dis[lvl[current]][X[i]]); else small[current] = dis[lvl[current]][X[i]], upd[current] = qcnt; current = par[current]; } } ll best = LONG_MAX; for(int i=0; i<s2; i++){ int current = Y[i]; while(current != -1){ if(upd[current] == qcnt) best = min(best,dis[lvl[current]][Y[i]]+small[current]); current = par[current]; } } return best; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...