# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101117 | 2019-03-16T17:18:10 Z | gs14004 | City (JOI17_city) | C++17 | 0 ms | 0 KB |
#include "Encoder.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 250005; vector<int> gph[MAXN]; int dfn[MAXN], sz[MAXN], piv; void dfs(int x, int p){ sz[x] = 1; dfn[x] = ++piv; for(auto &i : gph[x]){ if(i != p){ dfs(i, x); sz[x] += sz[i]; } } } void Encode(int N, int A[], int B[]){ for(int i=0; i<N-1; i++){ gph[A[i]].push_back(B[i]); gph[B[i]].push_back(A[i]); } dfs(0, -1); for (int i = 0; i < N; ++i) { Code(i, ((long long)dfn[i] << 18) + sz[i]); } }