Submission #384300

#TimeUsernameProblemLanguageResultExecution timeMemory
384300shivensinha4Factories (JOI14_factories)C++17
100 / 100
5433 ms496388 KiB
#include "bits/stdc++.h" using namespace std; #define for_(i, s, e) for (int i = s; i < e; i++) #define for__(i, s, e) for (ll i = s; i < e; i++) #define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str() typedef long long ll; typedef vector<int> vi; typedef pair<int, int> ii; #define endl '\n' #ifndef mlocal #include "factories.h" #endif class SparseTable { vector<vector<array<int, 2>>> st; int n; void buildTable(vector<array<int, 2>> &raw) { int k = __lg(n)+1; st.resize(n, vector<array<int, 2>> (k)); for_(i, 0, n) st[i][0] = raw[i]; for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1) st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]); } public: void build(vector<array<int, 2>> &nums) { n = nums.size(); buildTable(nums); } int mn(int l, int r) { int p = __lg(r-l+1); return min(st[l][p], st[r - (1<<p) + 1][p])[1]; } }; int n; vector<vector<array<ll, 2>>> adjList; vi removed, subtreeSize, centroid, tin, depth; vector<ll> rootDist, whiteDist; vector<vector<ll>> centroidDist; vector<array<int, 2>> tour; SparseTable st; const ll INF = 1e15; int dfs(int p, int parent) { int s = 1; tin[p] = tour.size(); tour.push_back({depth[p], p}); for (auto i: adjList[p]) if (i[0] != parent) { rootDist[i[0]] = rootDist[p]+i[1]; depth[i[0]] = depth[p]+1; s += dfs(i[0], p); tour.push_back({depth[p], p}); } subtreeSize[p] = s; return s; } int lca(int u, int v) { return st.mn(min(tin[u], tin[v]), max(tin[u], tin[v])); } ll dist(int u, int v) { int lc = lca(u, v); return rootDist[u] + rootDist[v] - 2*rootDist[lc]; } void noteCentroidDist(int p, int parent) { ll d = centroidDist[p].back(); for (auto i: adjList[p]) if (!removed[i[0]] and i[0] != parent) { centroidDist[i[0]].push_back(d+i[1]); noteCentroidDist(i[0], p); } } void decompose(int p, int c) { int invalidChild = -1, sizeLimit = (subtreeSize[p] >> 1); for (auto i: adjList[p]) if (!removed[i[0]] and subtreeSize[i[0]] > sizeLimit) { invalidChild = i[0]; break; } if (invalidChild != -1) { subtreeSize[p] -= subtreeSize[invalidChild]; subtreeSize[invalidChild] += subtreeSize[p]; return decompose(invalidChild, c); } removed[p] = true; centroid[p] = c; centroidDist[p].push_back(0); noteCentroidDist(p, p); for (auto i: adjList[p]) if (!removed[i[0]]) { centroid[i[0]] = p; decompose(i[0], p); } } vi updated; int pt = 0; void update(int p) { int v = p, cpt = (int) centroidDist[p].size() - 1; while (v != -1) { ll d = centroidDist[p][cpt--]; whiteDist[v] = min(whiteDist[v], d); updated[pt++] = v; v = centroid[v]; } } ll ans(int p) { ll val = INF; int v = p, cpt = (int) centroidDist[p].size() - 1; while (v != -1) { val = min(val, whiteDist[v] + centroidDist[p][cpt--]); v = centroid[v]; } return (val == 1e9 ? -1 : val); } void Init(int N, int A[], int B[], int D[]) { n = N; adjList.resize(n); subtreeSize.resize(n); removed.resize(n); centroid.resize(n, -1); depth.resize(n); tin.resize(n); rootDist.resize(n); whiteDist.resize(n, INF); updated.resize(10*n); centroidDist.resize(n); for_(i, 0, n-1) { int a = A[i], b = B[i]; ll w = D[i]; adjList[a].push_back({b, w}); adjList[b].push_back({a, w}); } dfs(0, 0); decompose(0, -1); st.build(tour); } ll Query(int S, int X[], int T, int Y[]) { pt = 0; for_(i, 0, S) update(X[i]); ll val = INF; for_(i, 0, T) val = min(val, ans(Y[i])); for_(i, 0, pt) whiteDist[updated[i]] = INF; return val; } #ifdef mlocal int main() { freopen("test.in", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(0); int N, q; cin >> N >> q; int A[100], B[100], D[100]; for_(i, 0, N - 1) { int a, b, w; cin >> a >> b >> w; A[i] = a; B[i] = b; D[i] = w; } Init(N, A, B, D); int X[100], Y[100]; while (q--) { int S, T; cin >> S >> T; for_(i, 0, S) cin >> X[i]; for_(i, 0, T) cin >> Y[i]; cout << Query(S, X, T, Y) << endl; } return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...