Submission #386556

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
386556	2021-04-06 19:32:51	PurpleCrayon	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	695 ms	44996 KiB

meetings2

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;
#define ar array
#define sz(v) int(v.size())
const int MAXN = 2e5+10, MAXL = 18, INF = 1e9+10;
int n, depth[MAXN], anc[MAXN][MAXL], st[MAXN], en[MAXN], tt=0;
vector<int> adj[MAXN];
//start lca
void init_lca(int c=0, int p=-1, int d=0){
  depth[c]=d, anc[c][0]=p;
    st[c] = tt++;
  for (int i=1; i < MAXL; i++) anc[c][i] = (anc[c][i-1]==-1?-1:anc[anc[c][i-1]][i-1]);
  for (auto nxt : adj[c]) if (nxt != p) init_lca(nxt, c, d+1);
    en[c] = tt-1;
}
int jmp(int a, int h){
  for (int i = 0; i < MAXL; i++) if ((h>>i)&1) a = anc[a][i];
  return a;
}
int lca(int a, int b){
  if (depth[a] < depth[b]) swap(a, b);
  a = jmp(a, depth[a]-depth[b]);
  if (a==b) return a;
  for (int i = MAXL-1; i >= 0; i--){
    if (anc[a][i] != anc[b][i]) a = anc[a][i], b = anc[b][i];
  }
  assert(anc[a][0]==anc[b][0]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80