Submission #971271

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
971271	2024-04-28 09:27:40	huutuan	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	408 ms	53260 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;
const int N=2e5+10, LG=18;
int n, sz[N], ans[N], dep[N], up[LG][N], tin[N], tout[N], tdfs, par[N];
vector<int> g[N], vv[N];
int mxdep[N];
void dfs(int u, int p){
   tin[u]=++tdfs;
   dep[u]=dep[p]+1;
   par[u]=p;
   for (int k=1; k<LG; ++k) up[k][u]=up[k-1][up[k-1][u]];
   for (int v:g[u]) if (v!=p){
      up[0][v]=u;
      dfs(v, u);
   }
   tout[u]=tdfs;
}
int lca(int u, int v){
   if (dep[u]!=dep[v]){
      if (dep[u]<dep[v]) swap(u, v);
      int d=dep[u]-dep[v];
      for (int k=0; k<LG; ++k) if (d>>k&1) u=up[k][u];
   }
   if (u==v) return u;
   for (int k=LG-1; k>=0; --k) if (up[k][u]!=up[k][v]) u=up[k][u], v=up[k][v];
   return up[0][u];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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