| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 780087 | cheat_when_I_was_young | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int NM = 5e5 + 5;
int in[NM], d[NM], h[NM];
vector<int> tour;
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);
}
}
const int LG = __lg(NM) + 1;
pair<int,int> ST[LG][NM];
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;
}
int color[NM], dp[NM][3], ans;
vector<int> newAdj[NM], node;
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;
}