Submission #555519

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
555519	2022-05-01 07:12:33	xdfactor2034	Race (IOI11_race)	C++17	0 / 100	7 ms	9940 KiB

race

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/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int mxN = 2e5+5;
using pii = pair<int,int>;
vector<pii> tr[mxN];
int N, K, res = LLONG_MAX, tin[mxN],tout[mxN], jump[mxN][19], lr[mxN], dr[mxN], dep, di, timer;
bool anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
void dfs(int x, int p) {
  dep++;
  lr[x] = dep, dr[x] = di, tin[x] = ++timer, jump[x][0] = p;
  for(int i = 1; i <= 18; i++) jump[x][i] = jump[jump[x][i-1]][i-1];
  for(auto it : tr[x]) if(it.second != p) {
    di += it.first;
    dfs(it.second,x);
    di -= it.first;
  }
  dep--, tout[x] = ++timer;
}
int lca(int u, int v) {
  if(anc(u,v))return u;
  if(anc(v,u))return v;
  for(int i = 18; i >= 0; i--) if(!anc(jump[u][i],v)) u = jump[u][i];
  return jump[u][0];
}
int len(int u, int v) {
  return lr[u]+lr[v]-2*lr[lca(u,v)];
}
int dist(int u, int v) { return dr[u]+dr[v]-2*dr[lca(u,v)]; }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57