| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 255754 | islingr | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a); )
#define sz(x...) int((x).size())
#define all(x) begin(x), end(x)
#define eb(x...) emplace_back(x)
#define lb(x...) lower_bound(x)
template<class T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
using ll = int64_t;
const ll inf = 1e18;
const int B = 19, N = 1 << B;
int dep[N], p[N][B], in[N];
ll dist[N];
void Init(int n, int a[], int b[], int d[]) {
vector<vector<int>> g(n);
rep(e, 0, n - 1) g[a[e]].eb(e), g[b[e]].eb(e);
int timer = 0;
function<void(int)> dfs = [&](int u) {
in[u] = timer++;
for (int e : g[u]) {
int v = u != a[e] ? a[e] : b[e];
if (v == p[u][0]) continue;
dist[v] = dist[u] + d[e];
dep[v] = dep[u] + 1;
p[v][0] = u;
rep(j, 0, B - 1) p[v][j + 1] = p[p[v][j]][j];
dfs(v);
}
};
dfs(0);
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
per(j, 0, B) if (dep[v] <= dep[p[u][j]]) u = p[u][j];
if (u == v) return u;
per(j, 0, B) if (p[u][j] != p[v][j]) u = p[u][j], v = p[v][j];
return p[u][0];
}
vector<int> g[N];
short col[N];
ll s[N], t[N];
ll Query(int S, vector<int> &X, int T, vector<int> &Y) {
vector<int> V; V.reserve(S + T);
for (int x : X) col[x] = +1, V.eb(x);
for (int y : Y) col[y] = -1, V.eb(y);
sort(all(V), [&](int x, int y) { return in[x] < in[y]; });
rep(i, 1, S + T) V.eb(lca(V[i - 1], V[i]));
sort(all(V), [&](int x, int y) { return in[x] < in[y]; });
V.erase(unique(all(V)), end(V));
rep(i, 1, sz(V)) g[lca(V[i - 1], V[i])].eb(V[i]);
ll ans = inf;
function<void(int)> dfs = [&](int u) {
s[u] = t[u] = inf;
if (col[u] > 0) s[u] = 0;
if (col[u] < 0) t[u] = 0;
for (int v : g[u]) {
dfs(v);
ckmin(s[u], dist[v] - dist[u] + s[v]);
ckmin(t[u], dist[v] - dist[u] + t[v]);
}
ckmin(ans, s[u] + t[u]);
};
dfs(V[0]);
for (int v : V) g[v].clear(), col[v] = 0;
return ans;
}