# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
92054 | Kamisama | Rice Hub (IOI11_ricehub) | C++14 | 0 ms | 0 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 <iostream>
#include <vector>
using namespace std;
const int maxn=1e5+7;
int n,m;
int par[maxn],lv[maxn],f[maxn][18];
int in[maxn],out[maxn],bit[maxn],dp[maxn];
vector<int> adj[maxn],road[maxn];
struct Query{int a,b,c;}q[maxn];
inline void Dfs(const int &u,const int &p){
static int nVisit=0;
in[u]=++nVisit;
par[u]=p;
lv[u]=lv[p]+1;
f[u][0]=p;
for(int i=1;i<18;i++) f[u][i]=f[f[u][i-1]][i-1];
for(int v: adj[u]) if(v!=p) Dfs(v,u);
out[u]=nVisit;
}
inline int Jump(int u,int k){for(int cur=0;k;k>>=1,cur++) if(k&1) u=f[u][cur];return u;}
inline int Lca(int u,int v){
if(lv[u]>lv[v]) swap(u,v);
v=Jump(v,lv[v]-lv[u]);
if(u==v) return u;
for(int i=17;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return par[u];
}
inline void Update(int x,const int &val){for(;x<=n;x+=x&-x) bit[x]+=val;}
inline int Get(int x){int res=0;for(;x;x-=x&-x) res+=bit[x];return res;}
inline void Solve(const int &u,const int &p){