oj.uz

Submission #816278

# Submission time Handle Problem Language Result Execution time Memory
816278 2023-08-09T04:40:14 Z 이동현(#10127) Marshmallow Molecules (CCO19_day2problem2) C++17
5 / 25
 73 ms 17264 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Dsu{
    int n;
    vector<int> pr, pqsize;
    vector<priority_queue<int, vector<int>, greater<int>>> pq;

    Dsu(int m){
        n = m + 4;
        pr.resize(n);
        pq.resize(n);
        pqsize.resize(n);
        iota(pr.begin(), pr.end(), 0);
    }

    int fd(int x){
        return x == pr[x] ? x : pr[x] = fd(pr[x]);
    }

    void unite(int x, int y){
        x = fd(x), y = fd(y);
        if(x == y) return;

        if(pqsize[x] < pqsize[y]){
            swap(x, y);
        }

        pqsize[x] += pqsize[y];
        pr[y] = x;
        while((int)pq[y].size()){
            pq[x].push(pq[y].top());
            pq[y].pop();
        }
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> r(n), l(n);
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        r[x].push_back(y);
        l[y].push_back(x);
    }

    Dsu gr(n);
    for(int i = 0; i < n; ++i){
        for(auto&nxt:r[i]){
            gr.pq[i].push(nxt);
            ++gr.pqsize[i];
        }
    }

    int ans = 0;
    for(int i = 0; i < n; ++i){
        for(auto&nxt:l[i]){
            gr.unite(nxt, i);
        }

        int rt = gr.fd(i);
        while(gr.pqsize[rt] && gr.pq[rt].top() <= i){
            --gr.pqsize[rt];
            gr.pq[rt].pop();
        }

        ans += gr.pqsize[rt];
    }

    cout << ans << '\n';
    
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16836 KB Output is correct
2 Correct 65 ms 17232 KB Output is correct
3 Correct 48 ms 17236 KB Output is correct
4 Correct 45 ms 16224 KB Output is correct
5 Correct 73 ms 17164 KB Output is correct
6 Correct 56 ms 17232 KB Output is correct
7 Correct 54 ms 16852 KB Output is correct
8 Correct 62 ms 17184 KB Output is correct
9 Correct 62 ms 17168 KB Output is correct
10 Correct 60 ms 16836 KB Output is correct
11 Correct 59 ms 17212 KB Output is correct
12 Correct 50 ms 17264 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -