Submission #679542

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
679542	2023-01-08 13:11:36	Dan4Life	Swapping Cities (APIO20_swap)	C++17	6 / 100	479 ms	82756 KiB

swap

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 "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = (int)5e5+10;
const int lgn = 20;
int n, m, num;
bool good[maxn];
int jmp[lgn][maxn], goodd[lgn][maxn];
vector<int> adj[maxn];
struct Edge{ int u, v, w; };
int p[maxn], lev[maxn], wei[maxn], deg[maxn];
Edge edge[maxn];
int getPath(int x, int steps){
  for(int i = lgn-1; i >= 0; i--)
    if(steps&(1<<i) and x!=-1) x = jmp[i][x];
  return x; 
}
int lca(int a, int b){
  if(a==b) return a;
  if(jmp[0][a]==jmp[0][b]) return jmp[0][a];
  if(lev[a] < lev[b]) swap(a,b);
  a = getPath(a, lev[a]-lev[b]);
  for(int i = lgn-1; i >= 0; i--)
    if(jmp[i][a]!=-1 and jmp[i][a]!=jmp[i][b])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27