Submission #1218030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218030		Gray	Port Facility (JOI17_port_facility)	C++20	22 / 100	6091 ms	30024 KiB

port_facility

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define ld long double
#define ff first
#define ss second
#define ln "\n"

const ll MOD = 1e9+7;

struct DSU{
    vector<ll> p; vector<unordered_map<ll, ll>> nodes;
    ll n, cnt;
    DSU(ll N){
        n=N; cnt=N; p.resize(n, -1);
        nodes.resize(n);
        for (ll i=0; i<n; i++) nodes[i][i]=0;
    }
    ll get(ll x){
        return p[x]==-1?x:p[x]=get(p[x]);
    }
    bool unite(ll u, ll v){
        // cout << cntt++ << ln;
        ll iu=u, iv=v;
        u=get(u); v=get(v);
        if (u==v){
            return nodes[u][iu]!=nodes[u][iv];
        }
        if (nodes[u].size()<nodes[v].size()) swap(u, v), swap(iu, iv);
        p[v]=u;
        if (nodes[u][iu]==nodes[v][iv]){
            for (auto &[x, val]:nodes[v]){
                val^=1;
            }
        }
        for (auto [x, val]:nodes[v]) nodes[u][x]=val;
        nodes[v].clear(); cnt--; return 1;
    }
};

void solve(){
    ll n; cin >> n;
    vector<ll> a(2*n+1);
    vector<array<ll, 2>> rng(n);
    for (ll i=0; i<n; i++){
        ll l, r; cin >> l >> r;
        a[l]=i; a[r]=i; rng[i] = {l, r};
    }
    set<array<ll, 2>> present;
    DSU tr(n);
    for (ll i=1; i<=2*n; i++){
        if (!present.count({rng[a[i]][1], a[i]})){
            for (auto [r, ind]:present){
                if (r>rng[a[i]][1]) break;
                if (!tr.unite(ind, a[i])){
                    cout << 0 << ln; return;
                }
            }
            present.insert({rng[a[i]][1], a[i]});
        }else{
            present.erase({rng[a[i]][1], a[i]});
        }
    }
    ll res=1;
    for (ll i=0; i<tr.cnt; i++) res=(res*2)%MOD;
    cout << res << ln;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) solve();
}

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