# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
955655 | Alexabcde1 | Railway (BOI17_railway) | C++14 | 226 ms | 70604 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>
#define f first
#define s second
using namespace std;
long long n,m,k,aa,bb,cnt,ind[100005],t,timer,in[100005],out[100005],par[100005][50],psum[100005],vis[100005],vis2[100005];
vector<pair<long long,long long> > ve;
vector<long long> adj[100005];
map<pair<long long,long long>,long long> mp;
vector<long long> ans;
void dfs(long long x,long long pre){
vis[x]=1;
in[x]=timer; timer++;
par[x][0]=pre;
for (int i=1;i<=40;i++) par[x][i]=par[par[x][i-1]][i-1];
cnt++;
ind[x]=cnt;
for (int ii=0;ii<adj[x].size();ii++){
if (!vis[adj[x][ii]]) dfs(adj[x][ii],x);
}
out[x]=timer; timer++;
return;
}
bool an(long long u,long long v){
return in[u]<=in[v] && out[u]>=out[v];
}
long long lca(long long u,long long v){
if (an(u,v)) return u;
if (an(v,u)) return v;
for (int i=39;i>=0;--i){
if (!an(par[u][i],v)) u=par[u][i];
Compilation message (stderr)
# | 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... |