Submission #439668

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
439668	2021-06-30 13:50:13	Ya_Ali	Railway (BOI17_railway)	C++17	100 / 100	165 ms	34208 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 *** ** */
// Only Haider is Amir al-Momenin
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10, lg = 17;
const ll mod = 1e9 + 7;
#define endl '\n'
ll tin [maxn], tout [maxn], anc [maxn][lg], H [maxn], khar_and_mother [maxn], tala [maxn], T, n, m, k;
vector <pair<ll, ll>> g [maxn];
vector <ll> A, ali;
void DFS (const ll &v = 1, const ll &pr = 1) {
  tin[v] = ++T;
  H[v] = H[pr] + 1;
  anc[v][0] = pr;
  for (ll i = 1; i < lg; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
  for (auto &u : g[v]) if (u.first != pr) DFS(u.first, v);
  tout[v] = T;
}
 
inline ll up (ll v, const ll &d) { for (ll i = lg; i--;) if (d >> i & 1) v = anc[v][i]; return v; }
inline ll lca (ll v, ll u) {
  if (H[v] > H[u]) swap(v, u);
  u = up(u, H[u] - H[v]);
  if (v == u) return v;
  for (ll i = lg; i--;) if (anc[v][i] ^ anc[u][i]) v = anc[v][i], u = anc[u][i];
  return anc[v][0];
}
 
void add (ll s) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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