Submission #779935

#TimeUsernameProblemLanguageResultExecution timeMemory
779935CDuongFactories (JOI14_factories)C++17
100 / 100
2214 ms289316 KiB
#include "factories.h" #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define pii pair<int, int> #define pil pair<int, ll> #define vi vector<int> #define vll vector<ll> #define vvi vector<vi> #define vii vector<pii> #define vil vector<pil> #define isz(x) (int)x.size() using namespace std; const int mxN = 5e5 + 5; const ll oo = 1e18; int n; vector<vii> G; vi vtn; vector<vil> vt; ll dis[mxN]; pii sparse[20][2 * mxN]; int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN]; void dfs(int v, int p) { tin[v] = ++timer; dep[v] = dep[p] + 1; sparse[0][++ecnt] = {dep[v], v}; ap[v] = ecnt; for(auto &[u, w] : G[v]) { if(u == p) continue; dis[u] = dis[v] + w; dfs(u, v); sparse[0][++ecnt] = {dep[v], v}; } tout[v] = timer; } void build_sparse() { for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i) for(int j = 1; j <= ecnt - (p << 1) + 1; ++j) sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]); } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int LCA(int u, int v) { int l = ap[u], r = ap[v]; if(l > r) swap(l, r); int len = r - l + 1, lg_len = __lg(len); return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss; } void Init(int N, int A[], int B[], int D[]) { n = N; G.resize(n); vt.resize(n); for(int i = 0; i < N - 1; ++i) { G[A[i]].emplace_back(B[i], D[i]); G[B[i]].emplace_back(A[i], D[i]); } dfs(0, 0); build_sparse(); } long long Query(int S, int X[], int T, int Y[]) { for(int i = 0; i < S; ++i) { cur[X[i]] = 1; vtn.emplace_back(X[i]); } for(int i = 0; i < T; ++i) { cur[Y[i]] = 2; vtn.emplace_back(Y[i]); } sort(all(vtn), [&](int u, int v) { return tin[u] < tin[v]; }); for(int i = 0; i < S + T - 1; ++i) { vtn.emplace_back(LCA(vtn[i], vtn[i + 1])); } sort(all(vtn), [&](int u, int v) { return tin[u] < tin[v]; }); vtn.erase(unique(all(vtn)), vtn.end()); auto add_vt = [&](int u, int v, ll w) { vt[u].emplace_back(v, w); vt[v].emplace_back(u, w); }; stack<int> s; for(int i = 0; i < isz(vtn); ++i) { while(not s.empty() && not is_ancestor(s.top(), vtn[i])) s.pop(); if(s.empty()) s.emplace(vtn[i]); else { add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]); s.emplace(vtn[i]); } } ll res = oo; auto dfs = [&](auto self, int v, int p) -> vll { vll cur_dis(2, oo); if(cur[v]) cur_dis[cur[v] - 1] = 0; for(auto &[u, w] : vt[v]) { if(u == p) continue; vll tmp = self(self, u, v); for(int i = 0; i < 2; ++i) cur_dis[i] = min(cur_dis[i], tmp[i] + w); } res = min(res, cur_dis[0] + cur_dis[1]); return cur_dis; }; dfs(dfs, vtn[0], 0); while(not vtn.empty()) { cur[vtn.back()] = 0; vt[vtn.back()].clear(); vtn.pop_back(); } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...