QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#797340 | #3251. 数正方体 | hcywoi | WA | 0ms | 3536kb | C++23 | 1.2kb | 2024-12-02 21:09:48 | 2024-12-02 21:09:49 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
struct DSU {
std::vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) {
std::iota(p.begin(), p.end(), 0);
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
sz[x] += sz[y], p[y] = x;
return true;
}
int size(int x) {
return sz[find(x)];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int L, R;
std::cin >> L >> R;
std::vector<std::tuple<i64, int, int>> e;
auto addEdge = [&](int x, int y) {
int t = (L + y - 1) / y;
if (t <= R / y && t * y != x) {
e.push_back({1LL * x * t, x, t * y});
}
};
for (int i = L; i <= R; i++) {
for (int j = 1; j <= i / j; j++) {
if (i % j == 0) {
addEdge(i, j);
if (j != i / j) {
addEdge(i, i / j);
}
}
}
}
std::sort(e.begin(), e.end());
DSU dsu(R + 1);
i64 ans = 0;
for (auto [w, u, v] : e) {
if (dsu.merge(u, v)) {
ans += w;
}
}
std::cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3536kb
input:
371 259 ......................................................................+---+---+.................................................................................................................................................................................... ...................................
output:
0
result:
wrong answer 1st lines differ - expected: '84826', found: '0'