| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 29224 | ruhanhabib39 | 공장들 (JOI14_factories) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
const int MAXLG = 20;
const long long INF = 1e18;
int N;
vector<pair<int,int>> G[MAXN + 10];
int cc[MAXN + 10];
int level[MAXN + 10];
long long dis[MAXLG + 10][MAXN + 10];
bool done[MAXN + 10];
int par[MAXN + 10];
void dfs0(int u, int p) {
cc[u] = 1;
for(auto e : G[u]) {
int v = e.first;
if(v == p || done[v]) continue;
dfs0(v, u);
cc[u] += cc[v];
}
}
void dfs(int u, int p, long long ds) {
// cerr << u << " " << p << " " << ds << "\n";
dis[++level[u]][u] = ds;
// cerr << "dis[" << level[u] << "][" << u << "] = " << dis[level[u]][u] << "\n";
for(auto e : G[u]) {
int v, d; tie(v, d) = e;
if(v == p || done[v]) continue;
dfs(v, u, ds + d);
}
}
int cnt;
int centroid(int u, int p) {
for(auto e : G[u]) {
int v = e.first;
if(v == p || done[v]) continue;
if(cc[v] > cnt/2) return centroid(v, u);
}
return u;
}
void decomp(int u, int p) {
dfs0(u, -1); cnt = cc[u];
u = centroid(u, -1); dfs(u, -1, 0);
// cerr << "centroid = " << u << "\n";
par[u] = p;
done[u] = true;
for(auto e : G[u]) {
int v = e.first;
if(done[v]) continue;
decomp(v, u);
}
}