Submission #702896

#	Time	Username	Problem	Language	Result	Execution time	Memory
702896		Dan4Life	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	340 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
#define all(a) a.begin(),a.end()
const int mxN = (int)2e6+2;
const int MOD = (int)1e9+7;
int n, a[mxN], cnt[mxN];

struct Dsu{
    vector<int> p, sz;
    int SZ;
    Dsu(int n): p(n,-1), sz(n,1), SZ(n){}

    int findSet(int i){return p[i]==-1?i:p[i]=findSet(p[i]); }
    bool isSameSet(int i, int j){return findSet(i)==findSet(j); }
    bool unionSet(int i, int j){
        int x = findSet(i), y = findSet(j);
        if(x==y) return false;
        if(sz[x]<sz[y]) swap(x,y);
        sz[x]+=sz[y], p[y]=x; SZ--;
        return true;
    }
};

int poww(int a, int b){
    if(!b) return 1;
    int x = poww(a,b/2);
    x*=x,x%=MOD;
    if(b&1)x*=a,x%=MOD;
    return x;
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        int x, y; cin >> x >> y;
        a[x]=a[y]=i;
    }
    set<pair<int,int>> S; Dsu dsu(n);
    for(int i = 1; i <= 2*n; i++){
        if(cnt[a[i]]){
            S.erase({cnt[a[i]],a[i]});
            auto itr = S.lower_bound(make_pair(cnt[a[i]],-1));
            while(itr!=S.end()){
                if(!dsu.unionSet(itr->se,a[i])){ cout << 0; return 0; }
                itr++;
            }
        }
        else S.insert({i,a[i]}),cnt[a[i]]=i;
    }
    cout << poww(2,dsu.SZ);
}

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