Submission #403638

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
403638	2021-05-13 10:34:21	saarang123	Railway (BOI17_railway)	C++17	100 / 100	144 ms	24920 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
#include <bits/stdc++.h>
using namespace std;
const int MXN = 100 * 1000 + 3;
const int LGN = 19;
vector<int> g[MXN];
int nxt[MXN], up[MXN][LGN], dt[MXN], tin[MXN], p[MXN];
int n, m, k;
void dfs(int v = 1, int pp = 1) {
  up[v][0] = pp;
  tin[v] = ++tin[0];
  for(int i = 1; i < LGN; ++i)
    up[v][i] = up[up[v][i - 1]][i - 1];
  for(int u : g[v]) if(u != pp) {
    dt[u] = dt[v] + 1;
    dfs(u, v);
  }
}
int kth(int v, int diff) {
  for(int i = 0; i < LGN; i++)
    if(diff >> i & 1)
      v = up[v][i];
  return v;
}
int LCA(int u, int v) {
  if(dt[u] > dt[v])
    swap(u, v);
  v = kth(v, dt[v] - dt[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