## Submission #1041310

# Submission time Handle Problem Language Result Execution time Memory
1041310 2024-08-01T20:59:30 Z sssamui Sirni (COCI17_sirni) C++17
98 / 140
5000 ms 405648 KB
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;

const ll one = 1;

vector<int> p(1e5);

int rt(int node)
{
if (p[node] == node) return node;
return p[node] = rt(p[node]);
}

void join(int a, int b)
{
p[rt(a)] = rt(b);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cin >> n;
set<int> ps;
while (n--)
{
int p;
cin >> p;
ps.insert(p);
}

vector<int> plst(0);
for (int p : ps) plst.push_back(p);
n = plst.size();
for (int i = 0; i < n; i++) p[i] = i;

map<int, int> inv;
for (int i = 0; i < n; i++) inv[plst[i]] = i;

vector<pair<int, pair<int, int>>> edg(0);
for (int p : ps)
{
auto it = ps.upper_bound(p);
while (it != ps.end())
{
int chk = *it;
edg.push_back({ chk % p, {inv[p], inv[chk]} });
chk += p;
chk /= p;
chk *= p;
it = ps.lower_bound(chk);
}
}

sort(edg.begin(), edg.end());
ll ans = 0;
for (pair<int, pair<int, int>> nxt : edg) if (rt(nxt.second.first) != rt(nxt.second.second))
{
ans += one * nxt.first;
join(nxt.second.first, nxt.second.second);
}

cout << ans;
}

#### Subtask #1 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 26 ms 4052 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct

#### Subtask #2 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 8 ms 1748 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct

#### Subtask #3 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct

#### Subtask #4 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 25404 KB Output is correct
2 Correct 1413 ms 60972 KB Output is correct
3 Correct 510 ms 34480 KB Output is correct

#### Subtask #5 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5316 KB Output is correct
2 Correct 411 ms 51924 KB Output is correct
3 Correct 386 ms 22028 KB Output is correct

#### Subtask #6 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 62336 KB Output is correct
2 Correct 1928 ms 109244 KB Output is correct
3 Correct 547 ms 36148 KB Output is correct

#### Subtask #7 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 11308 KB Output is correct
2 Correct 1521 ms 107300 KB Output is correct
3 Correct 458 ms 34864 KB Output is correct

#### Subtask #8 0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 37684 KB Output is correct
2 Execution timed out 5022 ms 405648 KB Time limit exceeded
3 Halted 0 ms 0 KB -

#### Subtask #9 0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 36400 KB Output is correct
2 Execution timed out 5068 ms 403816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

#### Subtask #10 0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 6084 KB Output is correct
2 Execution timed out 5082 ms 402808 KB Time limit exceeded
3 Halted 0 ms 0 KB -