# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
647825 | PoonYaPat | Railway (BOI17_railway) | C++14 | 149 ms | 31220 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,m,k,ord[100001],p[100001][18],cnt,sum[100001],level[100001];
vector<int> adj[100001],ans;
map<pii,int> mp;
void dfs(int x, int par) {
level[x]=level[par]+1;
p[x][0]=par;
for (int i=1; i<=17; ++i) p[x][i]=p[p[x][i-1]][i-1];
for (auto s : adj[x]) {
if (s==par) continue;
dfs(s,x);
}
ord[x]=++cnt;
}
int lca(int x, int y) {
if (level[x]<level[y]) swap(x,y);
int dif=level[x]-level[y];
for (int i=0; i<=17; ++i) {
if (dif&(1<<i)) x=p[x][i];
}
if (x==y) return x;
for (int i=17; i>=0; --i) {
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |