Submission #378259

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
378259	2021-03-16 10:53:24	Nima_Naderi	Railway (BOI17_railway)	C++14	100 / 100	262 ms	33756 KiB

railway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 1e5 + 10;
const ll LOG = 17;
ll n, q, m, k, timer;
ll Stm[MXN], val[MXN];
ll Jad[LOG][MXN], dis[MXN];
vector<pair<ll, ll>> Edge;
vector<ll> adj[MXN], S, ANS;
void prep(ll u, ll par){
  Jad[0][u] = par, Stm[u] = ++ timer;
  for(int i = 1; i < LOG; i ++) Jad[i][u] = Jad[i - 1][Jad[i - 1][u]];
  for(auto v : adj[u]){
    if(v != par) dis[v] = dis[u] + 1, prep(v, u);
  }
}
ll K_Jad(ll u, ll k){
  for(int i = 0; i < LOG; i ++){
    if((k >> i) & 1LL) u = Jad[i][u];
  }
  return u;
}
ll LCA(ll u, ll v){
  if(dis[u] > dis[v]) swap(u, v);
  v = K_Jad(v, dis[v] - dis[u]);
  if(u == v) return u;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25