| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 472968 | ngpin04 | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "grader.cpp"
#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int Nmax = 5e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = 3.14159265359;
vector <pair <int, int>> adj[Nmax];
long long d[Nmax];
long long mind[Nmax];
int t[2 * Nmax][20];
int tin[Nmax];
int par[Nmax];
int sz[Nmax];
int h[Nmax];
int timer;
bool bk[Nmax];
int getmin(int u, int v) {
return (h[u] < h[v]) ? u : v;
}
void dfs(int u, int p = -1) {
t[++timer][0] = u;
tin[u] = timer;
for (pair <int, int> to : adj[u]) {
int v = to.fi;
int w = to.se;
if (v == p)
continue;
h[v] = h[u] + 1;
d[v] = d[u] + w;
dfs(v, u);
t[++timer][0] = u;
}
}
void build() {
for (int j = 1; j < 20; j++)
for (int i = 1; i + (1 << j) - 1 <= timer; i++)
t[i][j] = getmin(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
}
long long dis(int u, int v) {
int l = tin[u];
int r = tin[v];
if (l > r)
swap(l, r);
int lg = log2(r - l + 1);
int p = getmin(t[l][lg], t[r - (1 << lg) + 1][lg]);
// cerr << u << " " << v << " " << p << "\n";
return d[u] + d[v] - (d[p] << 1);
}
int calc(int u, int p = -1) {
sz[u] = 1;
for (pair <int, int> to : adj[u]) {
int v = to.fi;
if (v == p || bk[v])
continue;
sz[u] += calc(v, u);
}
return sz[u];
}
int getcen(int u, int S, int p = -1) {
for (pair <int, int> to : adj[u]) {
int v = to.fi;
if (v == p || bk[v] || (sz[v] << 1) <= S)
continue;
return getcen(v, S, u);
}
return u;
}
int centroid(int u) {
int r = getcen(u, calc(u));
bk[r] = true;
for (pair <int, int> to : adj[r]) {
int v = to.fi;
if (bk[v])
continue;
par[centroid(v)] = r;
}
return r;
}
void Init(int n, int a[], int b[], int d[]) {
for (int i = 0; i < n - 1; i++) {
adj[a[i]].push_back(mp(b[i], d[i]));
adj[b[i]].push_back(mp(a[i], d[i]));
}
dfs(0);
build();
par[centroid(0)] = -1;
for (int i = 0; i < n; i++)
mind[i] = ooo;
}
void reset(int u) {
if (u < 0)
return;
mind[u] = ooo;
reset(par[u]);
}
void update(int u, int cur) {
if (cur < 0)
return;
// cerr << u << " " << cur << " " << dis(u, cur) << "\n";
mini(mind[cur], dis(u, cur));
update(u, par[cur]);
}
long long getans(int u, int cur) {
if (cur < 0)
return ooo;
// cerr << u << " " << cur << " " << dis(u, cur) << "\n";
long long res = mind[cur] + dis(u, cur);
mini(res, getans(u, par[cur]));
return res;
}
long long Query(int s, int x[], int t, int y[]) {
for (int i = 0; i < s; i++)
update(x[i], x[i]);
long long res = ooo;
for (int i = 0; i < t; i++)
mini(res, getans(y[i], y[i]));
for (int i = 0; i < s; i++)
reset(x[i]);
return res;
}