| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1156739 | nguyn | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
const int MN = 1e6 + 5;
const int inf = 1e18;
int n, q, tin[MN], tout[MN], h[MN], timedfs, f[MN][2], type[MN], s[MN], res;
pii rmq[21][MN];
vector<pii> g[MN];
vector<pii> g2[MN
void pre_dfs(int u, int p) {
tin[u] = ++timedfs;
rmq[0][timedfs] = {h[u], u};
for (auto it : g[u]) {
int v = it.F;
int w = it.S;
if (v == p) continue;
h[v] = h[u] + 1;
s[v] = s[u] + w;
pre_dfs(v, u);
rmq[0][++timedfs] = {h[u], u};
}
tout[u] = timedfs;
rmq[0][timedfs] = {h[u], u};
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
A[i]++, B[i]++;
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
for (int i = 1; i <= n; i++) type[i] = -1;
pre_dfs(1, 0);
for (int i = 1; i < 21; i++) {
for (int j = 1; j <= timedfs - (1 << i) + 1; j++) {
rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
}
}
}
bool in(int u, int v) {
return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v) {
int l = tin[u];
int r = tin[v];
if (l > r) swap(l, r);
int lg = __lg(r - l + 1);
// assert(l <= r);
return min(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]).S;
}
bool cmp(int u, int v) {
return tin[u] < tin[v];
}
void dfs(int u) {
f[u][0] = f[u][1] = inf;
if (type[u] != -1) {
f[u][type[u]] = 0;
}
for (auto it : g2[u]) {
int v = it.F;
int w = it.S;
dfs(v);
res = min({res, f[u][0] + w + f[v][1], f[u][1] + w + f[v][0]});
f[u][0] = min(f[u][0], f[v][0] + w);
f[u][1] = min(f[u][1], f[v][1] + w);
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> cur;
for (int i = 0; i < S; i++) {
cur.pb(X[i] + 1);
type[X[i] + 1] = 0;
}
for (int i = 0; i < T; i++) {
cur.pb(Y[i] + 1);
type[Y[i] + 1] = 1;
}
sort(cur.begin(), cur.end(), cmp);
int sz = cur.size() - 1;
for (int i = 0; i < sz; i++) {
// int l = lca(cur[i], cur[i + 1]);
// cout << cur[i] << ' ' << cur[i + 1] << ' ' << l << endl;
cur.pb(lca(cur[i], cur[i + 1]));
}
sort(cur.begin(), cur.end(), cmp);
cur.erase(unique(cur.begin(), cur.end()), cur.end());
stack<int> st;
for (int u : cur) {
while(!st.empty() && !in(st.top(), u)) {
st.pop();
}
if (!st.empty()) {
g2[st.top()].pb({u, s[u] - s[st.top()]});
// cout << st.top() << ' ' << u << ' ' << s[u] - s[st.top()] << endl;
}
st.push(u);
}
res = inf;
dfs(cur[0]);
for (int u : cur) {
g2[u].clear();
type[u] = -1;
}
return res;
}