제출 #414346

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
414346	2021-05-30 11:05:02	prvocislo	자매 도시 (APIO20_swap)	C++17	37 / 100	2058 ms	12084 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;
class dsu
{
public:
  vector<int> p, s, ok; // ok - je tento komponent cyklus alebo obsahuje rozvetvenie?
  int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
  void merge(int a, int b)
  {
    a = root(a), b = root(b);
    if (a == b) return ok[a] = true, void(); // cyklus
    if (s[a] < s[b]) swap(a, b);
    p[b] = a; s[a] += s[b];
    ok[a] |= ok[b]; 
  }
  void good(int u) { ok[root(u)] = true; }
  dsu(int n): p(vector<int>(n)), s(vector<int>(n, 1)), ok(vector<int>(n, false))
  {
    for (int i =0;i<n;i++) p[i] = i;
  }
};
struct edge { int u, v, w; };
bool cmp(edge a, edge b) { return a.w < b.w; }
int n, m;
vector<edge> e;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N, m = M;
  for (int i = 0; i < m;i++) e.push_back({U[i], V[i], W[i]}); 
  sort(e.begin(), e.end(), cmp);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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