| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 655492 | adaawf | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include "factories.h"
using namespace std;
int f[100005], ff[100005], a[100005], b[100005];
vector<pair<int, int>> g[100005], c[100005];
int vt[100005], in[100005], out[100005], cc[100005], h[100005], dd[100005], p[100005][21], t = 0;
bool cmp(int x, int y) {
return in[x] < in[y];
}
void dfs(int u, int x) {
t++;
in[u] = t;
p[u][0] = x;
for (int i = 1; i <= 20; i++) {
p[u][i] = p[p[u][i - 1]][i - 1];
}
for (auto w : g[u]) {
int v = w.first, k = w.second;
if (v != x) {
h[v] = h[u] + 1;
dd[v] = dd[u] + k;
dfs(v, u);
}
}
out[u] = t;
}
void dfs1(int u, int x) {
f[u] = a[u] = b[u] = 999999999;
for (auto w : c[u]) {
int v = w.first, k = w.second;
dfs1(v, u);
f[u] = min(f[v] + k, f[u]);
if (f[v] + k <= a[u]) {
b[u] = a[u];
a[u] = f[v] + k;
}
else if (f[v] + k <= b[u]) {
b[u] = f[v] + k;
}
}
if (vt[u] >= 2) f[u] = 0;
}
void dfs2(int u, int x, int y) {
ff[u] = 999999999;
if (vt[u] >= 2) ff[u] = 0;
else {
if (x != -1) {
if (vt[x] >= 2) ff[u] = y;
else {
if (f[u] + y == a[x]) ff[u] = b[x] + y;
else ff[u] = a[x] + y;
ff[u] = min(ff[u], ff[x] + y);
}
}
}
for (auto w : c[u]) {
int v = w.first, x = w.second;
dfs2(v, u, x);
}
}
int LCA(int u, int v) {
if (h[u] < h[v]) swap(u, v);
int lg = log2(h[u]) + 1;
for (int i = lg; i >= 0; i--) {
if (h[p[u][i]] >= h[v]) {
u = p[u][i];
}
}
if (u == v) return u;
for (int i = lg; i >= 0; i--) {
if (p[u][i] != p[v][i]) {
u = p[u][i];
v = p[v][i];
}
}
return p[u][0];
}
int trya(int u, int v) {
return dd[u] + dd[v] - dd[LCA(u, v)] * 2;
}
bool check(int x, int y) {
return (in[x] <= in[y]) && (out[y] <= out[x]);
}
void init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(1, 1);
}
long long int Query(int s, int x[], int t, int y[]) {
vector<int> v;
for (int i = 0; i < s; i++) {
v.push_back(x[i]);
vt[x[i]]++;
}
for (int i = 0; i < t; i++) {
v.push_back(y[i]);
vt[y[i]] += 2;
}
sort(v.begin(), v.end(), cmp);
int k = v.size();
for (int i = 1; i < k; i++) {
int g = LCA(v[i], v[i - 1]);
v.push_back(g);
}
sort(v.begin(), v.end(), cmp);
stack<int> s;
for (int i = 0; i < v.size(); i++) {
if (cc[v[i]] == 0) {
while (!s.empty() && (!check(s.top(), v[i]))) {
s.pop();
}
if (!s.empty()) c[s.top()].push_back({v[i], trya(s.top(), v[i])});
s.push(v[i]);
cc[v[i]] = 1;
}
}
dfs1(v[0], -1);
dfs2(v[0], -1, -1);
int res = 999999999;
for (int i = 0; i < v.size(); i++) {
if (vt[v[i]] == 1 || vt[v[i]] == 3) {
res = min(res, min(f[v[i]], ff[v[i]]));
}
}
for (int i = 0; i < v.size(); i++) {
cc[v[i]] = 0;
c[v[i]].clear();
vt[v[i]] = 0;
}
return res;
}