Submission #432016

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
432016	2021-06-17 19:07:50	pauloamed	Nafta (COI15_nafta)	C++14	34 / 100	1114 ms	311600 KiB

nafta

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;
#define MP make_pair
#define pii pair<int,int>
#define ppiii pair<pii,int>
#define FF first.first
#define FS first.second
#define MAXN 2010
struct DSU{
  vector<int> sizes, parents;
  DSU(int n){
    sizes = parents = vector<int>(n);
    for(int i = 0; i < n; ++i){
      sizes[i] = 1;
      parents[i] = i;
    }
  }
  int find(int current){
    int newRoot = current; // variavel para guardar nova raiz
    while(newRoot != parents[newRoot]) // enquanto nao encontro no raiz
    newRoot = parents[newRoot]; // subo na arvore
    // compressao de caminho (*) REMOVER SE FOR ROLLBACK
    int next; // backup do pai
    while(parents[current] != newRoot){ // enquanto nao acho a nova raiz
      next = parents[current]; // faco o backup do pai
      parents[current] = newRoot; // digo que o pai eh a raiz achada (*)
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

nafta.cpp: In member function 'int DSU::find(int)':
nafta.cpp:26:9: warning: variable 'next' set but not used [-Wunused-but-set-variable]
   26 |     int next; // backup do pai
      |         ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66