Submission #654580

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
654580	2022-10-31 19:05:51	atigun	Stranded Far From Home (BOI22_island)	C++14	100 / 100	298 ms	37996 KiB

island

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;
typedef long long ll;
struct dsu{
  vector<int> parent;
  vector<ll> sum;
  vector<vector<int>> S;
  int n;
  dsu(int dsu_size) : n(dsu_size){
    parent.resize(n+5);
    iota(parent.begin(), parent.end(), 0);
    sum.resize(n+5, 0);
    S.resize(n+5);
  }
  int find(int v){
    return parent[v] = (parent[v] == v ? v : find(parent[v]));
  }
  void merge(int v, int u){
    if(S[find(u)].size() > S[find(v)].size())
      swap(u, v);
    if(find(u) == find(v))
      return;
    for(int x : S[find(u)])
      S[find(v)].push_back(x);
    S[find(u)].clear();
    sum[find(v)]+= sum[find(u)];
    parent[find(u)] = parent[find(v)];
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35