QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258470#7749. A Simple MST Problemucup-team2307#TL 612ms107668kbC++201.5kb2023-11-19 18:28:162023-11-19 18:28:16

Judging History

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

  • [2023-11-19 18:28:16]
  • 评测
  • 测评结果:TL
  • 用时:612ms
  • 内存:107668kb
  • [2023-11-19 18:28:16]
  • 提交

answer

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct DSU {
    vector<int> e;
    DSU(int n) : e(n, -1) {}
    int find(int v) { return e[v] < 0 ? v : e[v] = find(e[v]); }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return 0;
        if(-e[u] < -e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        return 1;
    }
};

const int L = 1<<20;
int w[L];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    for(int x = 2; x < L; x++) {
        int ok = 1;
        for(int y = 2; ok && y * y <= x; y++) {
            if(x % y == 0) ok = 0;
        }
        if(ok) {
            for(int j = x; j < L; j += x)
                w[j]++;
        }
    }
    int T;
    cin >> T;
    while(T--) {
        int l, r;
        cin >> l >> r;
        vector<array<int, 3>> edges;
        for(int x = 1; x <= r; x++) {
            array<int, 2> cheapest {1<<30, 1<<30};
            for(int y = x; y <= r; y += x) if(y >= l) {
                cheapest = min(cheapest, {w[y], y});
            }
            for(int y = x; y <= r; y += x) if(y >= l) {
                edges.push_back({w[y] + cheapest[0] - w[x], cheapest[1], y});
            }
        }
        sort(all(edges));
        DSU D(r + 1);
        ll ans = 0;
        for(auto [cost, x, y] : edges)  {
            int t = D.join(x, y);
            ans += cost * t;
            // if(t) cout << x << " " << y << " add " << cost << endl;
        }
        cout << ans << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 133ms
memory: 7616kb

input:

5
1 1
4 5
1 4
1 9
19 810

output:

0
2
3
9
1812

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 213ms
memory: 20620kb

input:

2
27 30
183704 252609

output:

8
223092

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 216ms
memory: 20812kb

input:

1
183704 252609

output:

223092

result:

ok single line: '223092'

Test #4:

score: 0
Accepted
time: 612ms
memory: 107668kb

input:

2
639898 942309
30927 34660

output:

983228
11512

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 589ms
memory: 107256kb

input:

3
21731 33468
46192 370315
1712 3753

output:

34608
948775
5299

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 302ms
memory: 32000kb

input:

4
15237 67700
10918 86104
98287 116980
17432 23592

output:

148811
210927
60893
18687

result:

ok 4 lines

Test #7:

score: -100
Time Limit Exceeded

input:

5
5594 70302
19202 69588
5634 7877
59821 469300
97439 261121

output:

179735
145706
6565
1203684
488669

result: