Submission #743655

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
743655	2023-05-17 15:32:18	RushB	Swapping Cities (APIO20_swap)	C++17	36 / 100	444 ms	50348 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
//happier ending for folks like us? 
//yani in AC nashe, yak yak kesaii ke in APIO dadan dast ma
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 15, M = 2e5 + 5, L = 21, INF = 0x3f3f3f3f;
int p[N], dpr[N], pr[N][L], ext[N], P[N], h[N], rt, D[N], deg[N];
vector<int> adj[N], Wtmp;
inline void smin(int &a, int b) {a = min(a, b);}
void dfs(int v) {
  for (int i = 1; i < L; i++) pr[v][i] = pr[pr[v][i - 1]][i - 1];
  for (auto u: adj[v]) {
    pr[u][0] = v;
    h[u] = h[v] + 1;
    dfs(u);
    smin(ext[v], ext[u]);
  }
}
int gpr(int u) {return dpr[u] == u ? u : dpr[u] = gpr(dpr[u]);}
bool merge(int u, int v, int id) {
  int tu = u, tv = v;
  deg[tu]++, deg[tv]++;
  u = gpr(u), v = gpr(v);
  if (u == v) return false;
  dpr[u] = dpr[v] = id + M;
  D[id + M] = max({D[u], D[v], deg[tu], deg[tv]});
  adj[id + M].push_back(u);
  adj[id + M].push_back(v);
  return true;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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