#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long int
#define oo 1e9
#define pii pair<ll, int>
const int MAX = 1e5 + 5;
int n;
vector<array<int, 3>> edges;
int par[MAX];
int findSet(int u){
if(par[u] < 0) return u;
return par[u] = findSet(par[u]);
}
bool unite(int u, int v){
u = findSet(u);
v = findSet(v);
if(u == v) return false;
if(-par[u] < -par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
bool check(int u, int v){
u = findSet(u);
v = findSet(v);
if(u == v) return true;
return false;
}
void solve(){
memset(par, -1, sizeof(par));
cin >> n;
vector<int> v;
for (int i = 0; i < n; i++)
{
int a; cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
int m = v[v.size() - 1];
for (int i = 0; i < n; i++)
{
for (int r = 0; r <= m; r += v[i])
{
auto itr = lower_bound(v.begin(), v.end(), r);
if(itr == v.end()){
continue;
}
edges.push_back({(*itr) % v[i], i, int(itr - v.begin())});
}
}
sort(edges.begin(), edges.end());
int ans = 0;
for(array<int, 3> a : edges){
if(check(a[1], a[2])){
continue;
}
unite(a[1], a[2]);
ans += a[0];
}
cout << ans;
}
int main(){
solve();
}#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long int
#define oo 1e9
#define pii pair<ll, int>
const int MAX = 1e5 + 5;
int n;
vector<array<int, 3>> edges;
int par[MAX];
int findSet(int u){
if(par[u] < 0) return u;
return par[u] = findSet(par[u]);
}
bool unite(int u, int v){
u = findSet(u);
v = findSet(v);
if(u == v) return false;
if(-par[u] < -par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
bool check(int u, int v){
u = findSet(u);
v = findSet(v);
if(u == v) return true;
return false;
}
void solve(){
memset(par, -1, sizeof(par));
cin >> n;
vector<int> v;
for (int i = 0; i < n; i++)
{
int a; cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
int m = v[v.size() - 1];
for (int i = 0; i < n; i++)
{
for (int r = 0; r <= m; r += v[i])
{
auto itr = lower_bound(v.begin(), v.end(), r);
if(itr == v.end()){
continue;
}
edges.push_back({(*itr) % v[i], i, int(itr - v.begin())});
}
}
sort(edges.begin(), edges.end());
int ans = 0;
for(array<int, 3> a : edges){
if(check(a[1], a[2])){
continue;
}
unite(a[1], a[2]);
ans += a[0];
}
cout << ans;
}
int main(){
solve();
}
Compilation message
sirni.cpp:78:2: error: stray '#' in program
78 | }#include <bits/stdc++.h>
| ^
sirni.cpp:78:3: error: 'include' does not name a type
78 | }#include <bits/stdc++.h>
| ^~~~~~~
sirni.cpp:90:11: error: redefinition of 'const int MAX'
90 | const int MAX = 1e5 + 5;
| ^~~
sirni.cpp:13:11: note: 'const int MAX' previously defined here
13 | const int MAX = 1e5 + 5;
| ^~~
sirni.cpp:91:5: error: redefinition of 'int n'
91 | int n;
| ^
sirni.cpp:14:5: note: 'int n' previously declared here
14 | int n;
| ^
sirni.cpp:92:23: error: redefinition of 'std::vector<std::array<int, 3> > edges'
92 | vector<array<int, 3>> edges;
| ^~~~~
sirni.cpp:15:23: note: 'std::vector<std::array<int, 3> > edges' previously declared here
15 | vector<array<int, 3>> edges;
| ^~~~~
sirni.cpp:94:5: error: redefinition of 'int par [100005]'
94 | int par[MAX];
| ^~~
sirni.cpp:17:5: note: 'int par [100005]' previously declared here
17 | int par[MAX];
| ^~~
sirni.cpp:96:5: error: redefinition of 'int findSet(int)'
96 | int findSet(int u){
| ^~~~~~~
sirni.cpp:19:5: note: 'int findSet(int)' previously defined here
19 | int findSet(int u){
| ^~~~~~~
sirni.cpp:101:6: error: redefinition of 'bool unite(int, int)'
101 | bool unite(int u, int v){
| ^~~~~
sirni.cpp:24:6: note: 'bool unite(int, int)' previously defined here
24 | bool unite(int u, int v){
| ^~~~~
sirni.cpp:111:6: error: redefinition of 'bool check(int, int)'
111 | bool check(int u, int v){
| ^~~~~
sirni.cpp:34:6: note: 'bool check(int, int)' previously defined here
34 | bool check(int u, int v){
| ^~~~~
sirni.cpp:119:6: error: redefinition of 'void solve()'
119 | void solve(){
| ^~~~~
sirni.cpp:42:6: note: 'void solve()' previously defined here
42 | void solve(){
| ^~~~~
sirni.cpp:153:5: error: redefinition of 'int main()'
153 | int main(){
| ^~~~
sirni.cpp:76:5: note: 'int main()' previously defined here
76 | int main(){
| ^~~~
