Submission #467340

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
467340	2021-08-22 16:50:15	SirCovidThe19th	Swapping Cities (APIO20_swap)	C++17	6 / 100	411 ms	41464 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>
using namespace std; 
const int mx = 3e5 + 5;
int node, par[mx], up[mx][19], vals[mx], dep[mx]; bool ok[mx][19], cyc[mx]; 
vector<int> adj[mx];
int get(int i){
    return i == par[i] ? i : par[i] = get(par[i]);
}
void merge(int a, int b){
    a = get(a); b = get(b);
    cyc[node] = (a == b) or cyc[a] or cyc[b];
    adj[node].push_back(a); if (a != b) adj[node].push_back(b);
    par[a] = par[b] = node++;
}
void dfs(int i){
    for (int l = 1; l < 19; l++){
        up[i][l] = up[up[i][l - 1]][l - 1];
        ok[i][l] = ok[up[i][l - 1]][l - 1] | ok[i][l - 1];
    }
    for (auto x : adj[i]){
        up[x][0] = i; ok[x][0] = cyc[i];
        dep[x] = dep[i] + 1; dfs(x);
    }
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    int idx[m]; node = n + 1; iota(idx, idx + m, 0); iota(par, par + n + m + 1, 0); 
    sort(idx, idx + m, [&](int a, int b){ return w[a] < w[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