Submission #1144829

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

port_facility

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)1e6+10;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
const int MOD = (int)1e9+7;

int n, a[mxN], SZ, cnt[mxN];

template<int SZ>
struct WeightedDsu{
    int p[SZ], sz[SZ], w[SZ], cc;
    void init(int n){
        cc = 0;
        for(int i = 1; i <= n; i++)
            p[i]=i,sz[i]=1,w[i]=0,cc++;
    }
    int findSet(int i){
        if(i==p[i]) return i;
        int par = findSet(p[i]);
        w[i]^=w[p[i]];
        return p[i]=par;
    }
    void unionSet(int i, int j){
        int x = findSet(i), y = findSet(j);
        if(x==y){
            if(w[i]^w[j]^1){
                cout << 0 << "\n";
                exit(0);
            }
            return;
        }
        if(sz[x]<sz[y])swap(x,y);
        cc--; w[y]=w[x]^w[y]^1;
        sz[x]+=sz[y]; p[y]=x;
    }
};

WeightedDsu<mxN> dsu;

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; SZ=n; dsu.init(n);
    for(int i = 0; i < n; i++){
        int x, y; cin >> x >> y;
        a[x]=a[y]=i;
    }
    set<pair<int,int>> S;
    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()){
                dsu.unionSet(itr->se,a[i]); itr++; SZ--;
            }
        }
        else S.insert({i,a[i]}),cnt[a[i]]=i;
    }
    cout << poww(2,SZ);
}

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