제출 #1025695

#제출 시각아이디문제언어결과실행 시간메모리
1025695vjudge1공장들 (JOI14_factories)C++17
100 / 100
2895 ms252948 KiB
#include <bits/stdc++.h> #include "factories.h" #define ll long long #define ull unsigned long long #define ld long double #define pb push_back #define pf push_front #define vi vector<ll> #define vii vector<vi> #define pll pair<ll, ll> #define vpll vector<pll> #define all(a) a.begin(), a.end() #define fi first #define se second using namespace std; const ll mod = 1e9+7; const ll inf = 2e18; const ll blocksz = 320; const ll mxn = 1e6+8; vpll g[mxn],vg[mxn]; ll n,q,tin[mxn],tout[mxn],tdfs,h[mxn],up[mxn][20],d[mxn]; void dfs_pre(ll u, ll p){ tin[u] = ++tdfs; for(pll ed:g[u]){ ll v = ed.fi, w = ed.se; if(v == p) continue; h[v] = h[u]+1; d[v] = d[u]+w; up[v][0] = u; for(ll i = 1; i < 20; i++) up[v][i] = up[up[v][i-1]][i-1]; dfs_pre(v,u); } tout[u] = tdfs; } ll lca(ll u, ll v){ if(h[u] < h[v]) swap(u,v); ll k = h[u]-h[v]; for(ll i = 19; i >= 0; i--){ if(k>>i&1) u = up[u][i]; } if(u == v) return u; for(ll i = 19; i >= 0; i--){ if(up[u][i] != up[v][i]){ u = up[u][i]; v = up[v][i]; } } return up[u][0]; } ll dist(ll u, ll v){ return d[u]+d[v]-2*d[lca(u,v)]; } bool is_anc(ll u, ll v){ return tin[u] <= tin[v] && tout[v] <= tout[u]; } ll dp[mxn][2]; bool mark1[mxn],mark2[mxn]; void dfs(ll u, ll p){ dp[u][0] = inf, dp[u][1] = inf; if(mark1[u]) dp[u][0] = 0; if(mark2[u]) dp[u][1] = 0; for(pll ed:vg[u]){ ll v = ed.fi, w = ed.se; if(v == p) continue; dfs(v,u); dp[u][0] = min(dp[u][0],dp[v][0]+w); dp[u][1] = min(dp[u][1],dp[v][1]+w); } } void Init(int N, int A[], int B[], int D[]){ for(ll i = 0; i < N-1; i++){ g[A[i]].pb({B[i],D[i]}); g[B[i]].pb({A[i],D[i]}); } dfs_pre(0,-1); } long long Query(int S, int X[], int T, int Y[]){ vi vertex; for(ll i = 0; i < S; i++){ vertex.pb(X[i]); mark1[X[i]] = 1; } for(ll i = 0; i < T; i++){ vertex.pb(Y[i]); mark2[Y[i]] = 1; } sort(all(vertex),[&](ll u, ll v){ return tin[u] < tin[v]; }); ll m = vertex.size(); for(ll i = 1; i < m; i++){ ll l = lca(vertex[i-1],vertex[i]); vertex.pb(l); } sort(all(vertex),[&](ll u, ll v){ return tin[u] < tin[v]; }); vertex.erase(unique(all(vertex)),vertex.end()); stack<ll> st; for(ll v:vertex){ while(st.size() && !is_anc(st.top(),v)) st.pop(); if(st.size()){ vg[st.top()].pb({v,dist(v,st.top())}); vg[v].pb({st.top(),dist(v,st.top())}); } st.push(v); } dfs(vertex.front(),-1); ll ans = inf; for(ll v:vertex){ ans = min(ans,dp[v][0]+dp[v][1]); } for(ll v:vertex) vg[v].clear(),mark1[v] = mark2[v] = 0; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...