QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#255993 | #7749. A Simple MST Problem | ucup-team093# | TL | 910ms | 194788kb | C++17 | 2.8kb | 2023-11-18 17:40:28 | 2023-11-18 17:40:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e6 + 1;
int pf[N], w[N];
vector<int> primes;
vector<int> factors[N];
vector<int> nxt[N];
int cost[N], ctz[1 << 16];
bool vis[N];
struct smallpq{
vector<int> item[16];
int cnt = 0, msk = 0;
void push(const pii &a) {
item[a.first].push_back(a.second);
msk |= 1 << a.first;
cnt ++;
}
int size() {return cnt;}
pii top() {
int ptr = ctz[msk];
return {ptr, item[ptr].back()};
}
void pop() {
int ptr = ctz[msk];
item[ptr].pop_back();
cnt --;
if(item[ptr].empty()) msk ^= (1 << ptr);
}
} q;
int solve() {
int L, R;
cin >> L >> R;
for(int i = L + 1; i <= R; i ++)
vis[i] = false;
for(int i = 1; i <= R; i ++) {
nxt[i].clear();
for(int j = i; j <= R; j += i)
if(j > L) q.push({w[j], j});
while(q.size()) {
nxt[i].push_back(q.top().second);
q.pop();
}
reverse(nxt[i].begin(), nxt[i].end());
cost[i] = L % i == 0 ? w[L] - w[i] : w[L];
}
for(int i = 1; i * 2 <= R; i ++)
if(nxt[i].size()) q.push({w[nxt[i].back()] + cost[i], i});
int ans = 0;
while(q.size()) {
auto [c, p] = q.top();
q.pop();
if(nxt[p].empty() || c != cost[p] + w[nxt[p].back()]) continue;
int tar = -1;
if(!vis[nxt[p].back()]) {
vis[nxt[p].back()] = true;
tar = nxt[p].back();
ans += c;
}
while(nxt[p].size() && vis[nxt[p].back()])
nxt[p].pop_back();
if(nxt[p].size()) q.push({w[nxt[p].back()] + cost[p], p});
if(tar > 0)
for(auto fc : factors[tar])
if(cost[fc] > w[tar] - w[fc]) {
cost[fc] = w[tar] - w[fc];
if(nxt[fc].size()) q.push({w[nxt[fc].back()] + cost[fc], fc});
}
}
return ans;
}
int main() {
for(int i = 2; i < N; i ++) {
if(!pf[i]) {
pf[i] = i;
w[i] = 1;
primes.push_back(i);
}
for(int j : primes) {
if(i * (long long)j >= N) break;
pf[i * j] = j;
w[i * j] = w[i];
if(i % j == 0) break;
w[i * j] ++;
}
}
for(int i = 1; i < N; i ++)
for(int j = i; j < N; j += i)
factors[j].push_back(i);
for(int i = 0; i < 16; i ++)
ctz[1 << i] = i;
for(int i = 1; i < (1 << 16); i ++)
ctz[i] = ctz[i & -i];
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T --)
cout << solve() << "\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 617ms
memory: 150648kb
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: 681ms
memory: 157256kb
input:
2 27 30 183704 252609
output:
8 223092
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 674ms
memory: 159240kb
input:
1 183704 252609
output:
223092
result:
ok single line: '223092'
Test #4:
score: 0
Accepted
time: 910ms
memory: 194788kb
input:
2 639898 942309 30927 34660
output:
983228 11512
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 802ms
memory: 181704kb
input:
3 21731 33468 46192 370315 1712 3753
output:
34608 948775 5299
result:
ok 3 lines
Test #6:
score: 0
Accepted
time: 690ms
memory: 155848kb
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