Submission #683465

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
683465	2023-01-18 13:07:33	nguyentunglam	Swapping Cities (APIO20_swap)	C++14	53 / 100	420 ms	40932 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>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int lab[N], order[N], deg[N], noline[N], mx[N], h[N];
int par[18][N], f[18][N];
int cur;
vector<int> lst[N];
vector<pair<int, int> > adj[N];
int root(int v) {
    return lab[v] < 0 ? v : lab[v] = root(lab[v]);
}
void update(int u) {
    if (mx[u] <= 2) return;
    for(int j : lst[u]) noline[j] = cur;
    lst[u].clear();
}
bool join(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return 0;
    if (lab[u] > lab[v]) swap(u, v);
    mx[u] = max(mx[u], mx[v]);
    lab[u] += lab[v];
    for(int j : lst[v]) lst[u].push_back(j);
    lab[v] = u;
    return 1;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

swap.cpp: In function 'void dfs(int)':
swap.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for(auto [v, w] : adj[u]) if (v != par[0][u]) {
      |              ^

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