/*
https://github.com/mostafa-saad/MyCompetitiveProgramming/blob/master/Olympiad/COCI/official/2017/contest6_solutions/solutions.pdf
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=100000, INF=1000000000;
///500,000,000
int N, big, par[MAXN], siz[MAXN], pre;
bool skip[MAXN];
ll out;
set<int> inp;
vector<int> vals;
vector<pair<int, pair<int, int> > > edges; /// (weight, (n1, n2))
void make(int n1, int x, int add=0) {
int a = pre, b=N+1;
while (a != b) {
int mid = (a+b)/2;
if (vals[mid] >= x) b = mid;
else a = mid+1;
}
pre = a;
if (vals[a] == INF) return;
if (vals[a]-x+add == 0) skip[a] = true;
if (edges.size() > 0 && edges.back().b.a == n1 && edges.back().b.b == a) {
edges[edges.size()-1].a = vals[a]-x+add;
}
else edges.pb(mp(vals[a]-x+add, mp(n1, a)));
//w<< "connecting" s n1+1 s a+1 s x c vals[a]-x+add<<e;
}
int root (int x) {
if (par[x] == x) return x;
par[x] = root(par[x]);
return par[x];
}
int join(int a, int b) {
if (siz[a] > siz[b]) {
/// push b into a
siz[a] += siz[b];
par[b] = a;
}
else {
/// push a into b
siz[b] += siz[a];
par[a] = b;
}
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
ffi {int a; cin >> a; inp.insert(a); par[i] = i; siz[i] = 1;}
for (int i: inp) vals.pb(i); vals.pb(INF);
big = vals[vals.size()-2];
N = vals.size()-1;
ffi if (!skip[i]) {
pre = 0;
int x = vals[i];
make(i, x+1, 1);
for (int j=x+x; j<=big; j+=x) {
make(i, j);
}
}
sort(edges.begin(), edges.end());
for (auto i: edges) {
int cost = i.a, a = i.b.a, b = i.b.b;
if (root(a) == root(b)) continue;
out += cost;
join(par[a], par[b]); /// just called root so this should be fine
}
w<< out<<e;
}
Compilation message
sirni.cpp: In function 'int join(int, int)':
sirni.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
sirni.cpp: At global scope:
sirni.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
sirni.cpp: In function 'int main()':
sirni.cpp:69:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i: inp) vals.pb(i); vals.pb(INF);
^~~
sirni.cpp:69:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i: inp) vals.pb(i); vals.pb(INF);
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
508 KB |
Output is correct |
| 2 |
Correct |
74 ms |
3688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
632 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
221 ms |
18788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
2976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
356 ms |
31040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
59 ms |
5732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
318 ms |
31308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
325 ms |
31336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
46 ms |
4908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
