QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797340#3251. 数正方体hcywoiWA 0ms3536kbC++231.2kb2024-12-02 21:09:482024-12-02 21:09:49

Judging History

你现在查看的是最新测评结果

  • [2024-12-02 21:09:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3536kb
  • [2024-12-02 21:09:48]
  • 提交

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'