제출 #152321

#제출 시각아이디문제언어결과실행 시간메모리
152321karma공장들 (JOI14_factories)C++14
0 / 100
8087 ms24568 KiB
#include<bits/stdc++.h> #include "factories.h" #define pb emplace_back #define mp make_pair #define fi first #define se second #define ll long long using namespace std; const int N = int(5e5) + 7; const int logN = 21; const ll oo = (ll)1e18; typedef pair<int, int> pii; typedef pair<ll, ll> pll; static int in[N], out[N], h[N], p[N][logN], Ti, c[N]; ll d[N], res; pll f[N]; vector<pii> a[N], v; vector<int> g[N], st; void DFS(int u) { in[u] = ++Ti; for(int i = 1; i < logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1]; for(pii adj: a[u]) { if(in[adj.fi]) continue; d[adj.fi] = d[u] + adj.se; p[adj.fi][0] = u, h[adj.fi] = h[u] + 1; DFS(adj.fi); } out[u] = Ti; } int LCA(int u, int v) { if(h[u] < h[v]) swap(u, v); for(int i = logN - 1; i >= 0; --i) if(h[u] - (1 << i) >= h[v]) u = p[u][i]; if(u == v) return u; for(int i = logN - 1; i >= 0; --i) if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i]; return p[u][0]; } void Init(int n, int A[], int B[], int D[]) { for(int i = 0; i + 1 < n; ++i) a[A[i]].pb(B[i], D[i]), a[B[i]].pb(A[i], D[i]); DFS(0); } //fi - u, se - v void GetAns(int u) { if(c[u] == 1) f[u] = mp(d[u], oo); else if(c[u] == 2) f[u] = mp(oo, d[u]); else f[u] = mp(oo, oo); for(int v: g[u]) { GetAns(v); res = min({res, f[v].fi + f[u].se - 2 * d[u], f[v].se + f[u].fi - 2 * d[u]}); f[u].fi = min(f[u].fi, f[v].fi); f[u].se = min(f[u].se, f[v].se); } } ll Query(int S, int X[], int T, int Y[]) { v.clear(); st.clear(); for(int i = 0; i < S; ++i) g[X[i]].clear(), c[X[i]] = 1, v.pb(in[X[i]], X[i]); for(int i = 0; i < T; ++i) g[Y[i]].clear(), c[Y[i]] = 2, v.pb(in[Y[i]], Y[i]); sort(v.begin(), v.end()); for(int i = 0; i < S + T - 1; ++i) { int lca = LCA(v[i].se, v[i + 1].se); v.pb(in[lca], lca); } v.pb(in[0], 0); sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()); for(pii p: v) { while(!st.empty() && out[st.back()] < p.fi) st.pop_back(); if(st.size()) g[st.back()].pb(p.se); st.pb(p.se); } res = oo; GetAns(0); for(int i = 0; i < S; ++i) c[X[i]] = 0; for(int i = 0; i < T; ++i) c[Y[i]] = 0; return res; } // //int _n, q, A[N], B[N], D[N], S, T, X[N], Y[N]; // //int main() { // ios_base::sync_with_stdio(0); // cin.tie(0), cout.tie(0); // if(fopen("test.inp", "r")) { // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); // } // cin >> _n >> q; // for(int i = 0; i + 1 < _n; ++i) cin >> A[i] >> B[i] >> D[i]; // Init(_n, A, B, D); // for(int i = 0; i < q; ++i) { // cin >> S >> T; // for(int j = 0; j < S; ++j) cin >> X[j]; // for(int j = 0; j < T; ++j) cin >> Y[j]; // cout << Query(S, X, T, Y) << '\n'; // } //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...