Submission #878530

#TimeUsernameProblemLanguageResultExecution timeMemory
878530cpptowinFactories (JOI14_factories)C++17
15 / 100
8070 ms143684 KiB
#include"factories.h" #include<bits/stdc++.h> #define fo(i,d,c) for(int i=d;i<=c;i++) #define fod(i,c,d) for(int i=c;i>=d;i--) #define maxn 1000010 #define pb emplace_back #define inf 1000000000 #define pii pair<int,int > #define vii vector<pii> #define vi vector<int > using namespace std; vii ke[maxn]; int par[maxn][20],sz[maxn]; long long d[maxn]; int ind[maxn],head[maxn],cnt = 1; vector<array<long long,3>> adj[maxn]; void dfs(int u,int parent) { sz[u] = 1; for(auto [v,w] : ke[u]) { if(v == parent) continue; par[v][0] = u; d[v] = d[u] + w; dfs(v,u); sz[u] += sz[v]; } } void hld(int u,int parent) { if(head[cnt] == 0) head[cnt] = u; ind[u] = cnt; int sc = -1,maxx = -1; for(auto [v,w] : ke[u]) if(v != parent) { if(maxx < sz[v]) { maxx = sz[v]; sc = v; } } if(sc != -1) hld(sc,u); for(auto [v,w] : ke[u]) if(v != parent and v != sc) { cnt++; hld(v,u); } } void get(int u,int t) { long long val = d[u]; int uchain,vchain = ind[1]; while(1) { uchain = ind[u]; adj[uchain].push_back({u,val,t}); if(uchain == vchain) return; u = ind[u]; u = par[head[u]][0]; } } void Init(int N,int A[],int B[],int D[]) { fo(i,0,N - 2) { ke[A[i] + 1].pb(B[i] + 1,D[i]); ke[B[i] + 1].pb(A[i] + 1,D[i]); } dfs(1,1); hld(1,1); } long long Query(int S, int X[], int T, int Y[]) { long long ans = 2e18; fo(i,0,S - 1) get(X[i] + 1,0); fo(i,0,T - 1) get(Y[i] + 1,1); fo(i,1,cnt) { long long minn[2]; minn[0] = minn[1] = 2e18; sort(adj[i].begin(),adj[i].end(),[](array<long long,3> a,array<long long,3> b) { return d[a[0]] > d[b[0]]; }); for(auto [v,dist,t] : adj[i]) { ans = min(ans,minn[1 - t] - 2 * d[v] + dist); minn[t] = min(minn[t],dist); } adj[i].clear(); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...