| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 434057 | 2021-06-20T14:33:20 Z | kwongweng | 기지국 (IOI20_stations) | C++17 | 0 ms | 0 KB |
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define pb push_back
vector<vi> g;
vi ans, sz, d, used;
int cur = 0;
void dfs1(int u = 0, int p = -1){
for (int v : g[u]){
if (v == p) continue;
d[v] = d[u] + 1;
dfs1(v, u);
sz[u] += sz[v] + 1;
}
}
void dfs2(int u = 0, int p = -1){
if (d[u] % 2 == 0){
used[cur] = 1;
ans[u] = cur;
while (used[cur]) cur++;
}else{
used[cur+sz[u]] = 1;
ans[u] = cur+sz[u];
while (used[cur]) cur++;
}
for (int v : g[u]){
if (v == p) continue;
dfs2(v, u);
}
}
vi label(int n, int k, vi u, vi v) {
g.resize(n);
ans.resize(n); used.resize(n);
d.resize(n); sz.resize(n);
for (int i = 0; i < n-1; i++){
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
dfs1();
dfs2();
return ans;
}