| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 495561 | K4YAN | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Be Name Khoda
#include<bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
const ll mxn = 5e5 + 16, INF = 1e15 + 32;
ll n, m, q, w, ans;
ll st[mxn], fn[mxn], h[mxn], dis[mxn], c[mxn], dp[mxn][3], par[mxn][20];
vector<ll> f, g;
vector<pll> adj[mxn], G[mxn];
set<ll> s;
bitset<mxn> mark;
void DFS(int v) {
mark.set(v);
st[v] = q++, fn[v] = q, h[v] = w++;
for(int i = 1; i < 20; i++) {
par[v][i] = par[par[v][i - 1]][i - 1];
}
for(auto u : adj[v]) {
if(!mark[u.first]) {
par[u.first][0] = v;
dis[u.first] = h[v] + u.second;
DFS(u.first);
fn[v] = fn[u.first];
}
} w--;
}
inline void Init(int N, int A[], int B[], int D[]) {
n = N;
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(0);
mark.reset();
}
inline void clr() {
for(auto u : f) {
c[u] = 0;
} f.clear();
return;
}
bool comp(int a, int b) {
return st[a] < st[b];
}
ll find_lca(ll v, ll u) {
if(v == u) return v;
if(h[v] > h[u]) {
swap(v, u);
}
for(int i = 19; i > -1; i--) {
if(h[u] - (1LL << i) < h[v]) continue;
u = par[u][i];
}
if(v == u) return v;
for(int i = 19; i > -1; i--) {
if(par[u][i] != par[v][i]) {
u = par[u][i], v = par[v][i];
}
} return par[v][0];
}
inline void build_Graph() {
stack<ll> st;
st.push(g[0]); dp[g[0]][0] = dp[g[0]][1] = dp[g[0]][2] = INF;
for(int i = 1; i < int(g.size()); i++) {
while(fn[st.top()] < fn[f[i]]) st.pop();
dp[g[i]][0] = dp[g[i]][1] = dp[g[i]][2] = INF;
G[st.top()].push_back({f[i], dis[f[i]] - dis[st.top()]});
}
}
void solve_dp(int v) {
dp[v][c[v] % 2] = 0;
for(auto u : G[v]) {
solve_dp(u.first);
dp[v][2] = min(dp[v][2], dp[u.first][2]);
dp[v][1] = min(dp[v][1], dp[u.first][1] + u.second);
dp[v][0] = min(dp[v][0], dp[u.first][0] + u.second);
}
dp[v][2] = min(dp[v][2], dp[v][1] + dp[v][0]);
return;
}
inline ll Query(int S, int X[], int T, int Y[]) {
for(auto u : g) {
G[u].clear();
} clr(); s.clear(), f.clear(), g.clear();
for(int i = 0; i < S; i++) {
c[X[i]] = 1; f.push_back(X[i]); s.insert(X[i]);
} for(int i = 0; i < T; i++) {
c[Y[i]] += 2;
f.push_back(Y[i]); s.insert(Y[i]);
if(c[Y[i]] == 3) {
return 0;
}
}
sort(all(f), comp);
g = f;
for(int i = 0; i < int(f.size()) - 1; i++) {
w = find_lca(f[i], f[i + 1]);
if(!s.count(w)) {
s.insert(w);
g.push_back(w);
}
}
sort(all(g), comp);
build_Graph();
solve_dp(g[0]);
ans = dp[g[0]][2];
return ans;
}