Submission #1146194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146194		eggx50000	Port Facility (JOI17_port_facility)	C++20	10 / 100	94 ms	157000 KiB

port_facility

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int n, a, b;
int arr[2000099], brr[2000099], num[2000099];
set <int> maa[2000099];

struct Da{
    int u, v;
};

struct Ufo{
    int par[1000099], si[1000099];
    priority_queue <int> pq[1000099][2];

    Da fi(int a){
        if(par[a] == 0) return {a, 0};
        else{
            Da vv = fi(par[a]);
            si[a] = si[a] ^ vv.v;
            par[a] = vv.u;
            return {vv.u, si[a]};

        }
    }

    void uni(int a, int b){
        Da x = fi(a), y = fi(b);
        if(x.u == y.u){
            if(x.v == y.v){
                printf("0");
                exit(0);
            }
            return;
        }
        a = x.u, b = y.u;
        par[b] = a;
        si[b] = 1 - (x.v ^ y.v);
        for(int i = 0; i < 2; i ++){
            if(pq[a][i].size() < pq[b][i ^ si[b]].size()) swap(pq[a][i], pq[b][i ^ si[b]]);
            while(pq[b][i ^ si[b]].size()){
                pq[a][i].push(pq[b][i ^ si[b]].top());
                pq[b][i ^ si[b]].pop();
            }
        }
    }

} uff;
priority_queue <int> zpq;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d %d", &a, &b);
        arr[a] = b;
        brr[b] = a;
    }
    int cn = 0;
    for(int i = 1; i <= 2 * n; i ++){
        if(arr[i]){
            num[i] = ++cn;
            vector <int> vv;
            int p = 0;
            int ppp = 0;
            while(zpq.size() && -zpq.top() <= arr[i]){
                int p = -zpq.top();
                zpq.pop();
                if(p < i){
                    int nn = num[brr[p]];
                    Da jt = uff.fi(nn);
                    int v = uff.fi(num[brr[p]]).u;
                    if(uff.pq[v][jt.v].empty()) continue;
                    uff.pq[v][jt.v].pop();
                    if(!uff.pq[v][jt.v].empty()) zpq.push(uff.pq[v][jt.v].top());
                    continue;
                }
                vv.push_back(num[brr[p]]);
            }
            uff.pq[cn][0].push(-arr[i]);
            for(int &e : vv) uff.uni(cn, e);
            if(uff.pq[uff.fi(cn).u][0].size()) zpq.push(uff.pq[uff.fi(cn).u][0].top());
            if(uff.pq[uff.fi(cn).u][1].size()) zpq.push(uff.pq[uff.fi(cn).u][1].top());
        }
    }
    cn = 0;
    for(int i = 1; i <= n; i ++) if(uff.fi(i).u == i) cn ++;
    long long v = 1;
    long long mod = 1000000007;
    for(int i = 1; i <= cn; i ++){
        v *= 2;
        v %= mod;
    }
    printf("%lld", v);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
port_facility.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22