QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#255993#7749. A Simple MST Problemucup-team093#TL 910ms194788kbC++172.8kb2023-11-18 17:40:282023-11-18 17:40:28

Judging History

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

  • [2023-11-18 17:40:28]
  • 评测
  • 测评结果:TL
  • 用时:910ms
  • 内存:194788kb
  • [2023-11-18 17:40:28]
  • 提交

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

result: