QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258470 | #7749. A Simple MST Problem | ucup-team2307# | TL | 612ms | 107668kb | C++20 | 1.5kb | 2023-11-19 18:28:16 | 2023-11-19 18:28:16 |
Judging History
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