Submission #702926

#	Time	Username	Problem	Language	Result	Execution time	Memory
702926		Dan4Life	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	468 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)2e5+2;
const int MOD = (int)1e9+7;
int n, a[mxN], cnt[mxN];

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

    pair<int,int> findSet(int i){
        if(p[i].fi!=-1){
            int len = p[i].se;
            p[i] = findSet(p[i].fi);
            p[i].se ^= len;
        }
        return p[i];
    }

    bool isSameSet(int i, int j){return findSet(i).fi==findSet(j).fi; }
    bool unionSet(int i, int j){
        int x = findSet(i).fi, y = findSet(j).fi;
        int lx = findSet(i).se, ly = findSet(j).se;
        if(x==y){
            if(lx==ly) return bip[x]=false;
            return true;
        }
        if(sz[x]<sz[y]) swap(x,y);
        sz[x]+=sz[y], p[y]=mp(x,lx^ly^1); SZ--;
        bip[x]&=bip[y];
        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);
}

Compilation message (stderr)

port_facility.cpp: In member function 'bool Dsu::unionSet(long long int, long long int)':
port_facility.cpp:33:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |             if(lx==ly) return bip[x]=false;

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