Submission #1216807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216807		Gray	Port Facility (JOI17_port_facility)	C++20	22 / 100	1796 ms	1114112 KiB

port_facility

#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<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){
        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);
        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;
        cnt--; return 1;
    }
};

void dfs(ll u, vector<ll> &vis, vector<vector<ll>> &A, bool &pos){
    for (auto v:A[u]){
        if (vis[v]==-1) {
            vis[v]=vis[u]^1; dfs(v, vis, A, pos);
        }else {
            if (vis[v]==vis[u]) pos=0;
        }
    }
}

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);
    vector<vector<ll>> A(n+1);
    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;
                // }
                A[ind].push_back(a[i]); A[a[i]].push_back(ind);
            }
            present.insert({rng[a[i]][1], a[i]});
        }else{
            present.erase({rng[a[i]][1], a[i]});
        }
    }
    vector<ll> vis(n+1, -1);
    ll res=1; bool pos=1;
    for (ll i=0; i<n; i++){
        if (vis[i]==-1){
            vis[i]=0; res=(res*2)%MOD;
            dfs(i, vis, A, pos);
        }
    }
    cout << pos*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