| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 482004 | MilosMilutinovic | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back
#define xx first
#define yy second
#define pii pair<int,int>
#define ll long long
using namespace std;
int n;
int sajz[500005];
int par[500005][23];
vector<pii> graf[500005];
bool was[500005];
vector<pii> cale[500005];
int dub[500005];
ll dep[500005];
void dfs(int u, int p){
dub[u] = dub[p] + 1;
par[u][0] = p;
ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
for(auto c:graf[u]){
if(c.xx != p){
dep[c.xx] = dep[u] + c.yy;
dfs(c.xx, u);
}
}
}
int lca(int u, int v){
if(dub[u] < dub[v])swap(u, v);
fb(i,22,0){
if(dub[par[u][i]] >= dub[v])u = par[u][i];
}
//cout << u << " " << v << "\n";
assert(dub[u] == dub[v]);
fb(i,22,0){
if(par[u][i] != par[v][i]){
u = par[u][i];
v = par[v][i];
}
}
if(u != v){
u = par[u][0];
v = par[v][0];
}
assert(u == v);
return u;
}
ll dist(int u, int v){
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void dfs1(int u, int p){
sajz[u] = 1;
for(auto c:graf[u]){
if(c.xx == p || was[c.xx]) {
continue;
}
dfs1(c.xx, u);
sajz[u] += sajz[c.xx];
}
}
int dfs2(int u, int p, int n){
for(auto c:graf[u]){
if(!was[c.xx] && c.xx != p && sajz[c.xx] * 2 >= n) {
return dfs2(c.xx, u, n);
}
}
return u;
}
int findcen(int u){
dfs1(u, u);
return dfs2(u, u, sajz[u]);
}
void solve(int u, int p, int st, ll s){
cale[u].pb({st,s});
for(auto c:graf[u]){
if(c.xx != p && !was[c.xx]){
solve(c.xx, u, st, s + c.yy);
}
}
}
void decomp(int u) {
u = findcen(u);
solve(u, u, u, 0);
was[u] = true;
for(auto c:graf[u]){
if(!was[c.xx])decomp(c.xx);
}
}
ll mn[500005];
void Init(int N, int* A, int* B, int* D){
n = N;
ff(i,0,n-2){
A[i]++;
B[i]++;
graf[A[i]].pb({B[i], D[i]});
graf[B[i]].pb({A[i], D[i]});
}
dfs(1, 0);
decomp(1);
// ff(i,1,n) assert((int) cale[i].size() <= 50);
ff(i,1,n)mn[i] = 1e18;
}
ll Query(int S, int* X, int T, int* Y){
ll ans = 1e18;
ff(i,0,S-1)X[i]++;
ff(i,0,T-1)Y[i]++;
//ff(i,0,S-1) ff(j,0,T-1) ans = min(ans, dist(X[i], Y[j]));
vector<int> cv;
ff(i,0,S-1){
assert(cale[i].size() <= 40);
for(auto c:cale[X[i]]){
mn[c.xx] = min(mn[c.xx], c.yy);
}
}
ff(i,0,T-1){
for(auto c:cale[Y[i]]){
ans = min(ans, mn[c.xx] + c.yy);
}
}
for(auto c:cv)mn[c] = 1e18;
return ans;
}