Submission #788049

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
788049	2023-07-19 16:57:28	ToniB	Swapping Cities (APIO20_swap)	C++17	100 / 100	339 ms	46836 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 <bits/stdc++.h>
#include "swap.h"
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 2;
const int LOG = 18;
int n, m, cycle[MAXN], uf[MAXN], sz[MAXN], cnt[MAXN];
int dep[MAXN], bl[MAXN][LOG], bl_w[MAXN][LOG];
bool uf_bio[MAXN];
vector<pair<int, int> > adj[MAXN], tree[MAXN];
vector<pair<int, pii> > edges;
int f(int x){
  while(uf[x] != -1) x = uf[x];
  return x;
}
void join(int u, int v, int edge){
  if(uf_bio[u] ^ uf_bio[v]){
    if(uf_bio[v]) swap(u, v);
    cycle[v] = edge;
    uf_bio[v] = 1;
  }
  if(sz[u] > sz[v]) swap(u, v);
  sz[v] += sz[u];
  uf[u] = v;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

swap.cpp: In function 'int calc(int, int)':
swap.cpp:35:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |   if(dep[u] - dep[v] & 1 << i){
      |      ~~~~~~~^~~~~~~~

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