Submission #780101

#TimeUsernameProblemLanguageResultExecution timeMemory
780101cheat_when_I_was_young공장들 (JOI14_factories)C++17
0 / 100
3969 ms524288 KiB
#include "factories.h" #include "bits/stdc++.h" using namespace std; const int NM = 5e5 + 5; const int LG = __lg(NM) + 1; int in[NM], h[NM], color[NM]; long long d[NM], dp[NM][3], ans; pair<int,int> ST[LG][NM]; vector<int> tour, newAdj[NM], node; vector<pair<int,int>> adj[NM]; void dfs(int u, int par) { in[u] = tour.size(); tour.push_back(u); for (auto &vv: adj[u]) { int v = vv.first, w = vv.second; if (v == par) continue; d[v] = d[u] + w; h[v] = h[u] + 1; dfs(v, u); tour.push_back(u); } } void build() { for (int i = 0; i < (int)tour.size(); ++i) ST[0][i] = {h[tour[i]], tour[i]}; for (int j = 1; j < LG; ++j) for (int i = 0; i + (1<<j) - 1 < (int)tour.size(); ++i) ST[j][i] = min(ST[j-1][i], ST[j-1][i + (1<<(j-1))]); } int lca(int u, int v) { int l = in[u], r = in[v]; if (l > r) swap(l, r); int k = __lg(r - l + 1); return min(ST[k][l], ST[k][r - (1<<k) + 1]).second; } void Init(int N, int A[], int B[], int D[]) { for (int i = 0; i < N-1; ++i) { adj[A[i]].push_back({B[i], D[i]}); adj[B[i]].push_back({A[i], D[i]}); } dfs(1, 1); build(); ans = 1e18; for (int i = 0; i < N; ++i) dp[i][1] = dp[i][2] = 1e18; } bool cmp(int x, int y) { return in[x] < in[y]; } void DFS(int u, int par) { for (int &v: newAdj[u]) { if (v == par) continue; DFS(v, u); } ans = min(ans, dp[u][0] + dp[u][1]); } long long Query(int S, int X[], int T, int Y[]) { for (int i = 0; i < S; ++i) color[X[i]] = 1; for (int i = 0; i < T; ++i) { if (color[Y[i]] == 1) { for (int j = 0; j < S; ++j) color[X[j]] = 0; for (int j = 0; j < T; ++j) color[Y[j]] = 0; return 0; } color[Y[i]] = 2; } for (int i = 0; i < S; ++i) node.push_back(X[i]); for (int i = 0; i < T; ++i) node.push_back(Y[i]); sort(node.begin(), node.end()); int N = node.size(); for (int i = 1; i < N; ++i) node.push_back(lca(node[i], node[i-1])); sort(node.begin(), node.end()); stack<int> st; for (int &i: node) { if (st.empty()) { st.push(i); continue; } while (!st.empty() && lca(i, st.top()) != st.top()) st.pop(); if (!st.empty()) { newAdj[st.top()].push_back(i); newAdj[i].push_back(st.top()); st.push(i); } } DFS(node[0], node[0]); ans = 1e18; for (int &i: node) { color[i] = 0; dp[i][1] = dp[i][2] = 1e18; newAdj[i].clear(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...