Submission #1226517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226517		duckindog	Port Facility (JOI17_port_facility)	C++20	100 / 100	213 ms	83368 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int n;
pair<int, int> range[N];

namespace DSU { 
    int id[N], c[N];
    void init() { memset(id, -1, sizeof id); }
    int root(int u) { 
        if (id[u] < 0) return u;
        int p = root(id[u]);
        c[u] ^= c[id[u]];
        return id[u] = p;
    }
    int join(int u, int v) { 
        int rootU = root(u), rootV = root(v);
        if (id[rootU] > id[rootV]) swap(rootU, rootV);
        if (rootU == rootV) return c[u] ^ c[v];
        id[rootU] += id[rootV];
        id[rootV] = rootU;

        c[rootV] = c[u] ^ c[v] ^ 1;
        return 1;
    }
}

int type[N << 1], id[N << 1];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> range[i].first >> range[i].second;

    for (int i = 1; i <= n; ++i) { 
        type[range[i].first] = 1;
        id[range[i].first] = id[range[i].second] = i;
    }
    
    DSU::init();
    stack<list<int>> st;
    for (int i = 1; i <= 2 * n; ++i) { 
        if (type[i]) {
            st.push({});
            st.top().push_back(id[i]);
        } else { 
            list<int> vt;
            for (;;) { 
                if (st.top().back() == id[i]) { 
                    st.top().pop_back();
                    if (!st.top().size()) st.pop();
                    break;
                }
                if (!DSU::join(id[i], st.top().back())) { 
                    cout << 0 << "\n";
                    return 0;
                }
                vt.splice(vt.begin(), st.top());
                st.pop();
            }
            if (vt.size()) {
                st.push({});
                st.top().splice(st.top().begin(), vt);
            }
        }
    }

    int answer = 1;
    for (int i = 1; i <= n; ++i) { 
        if (DSU::id[i] < 0) answer = 1ll * answer * 2 % 1'000'000'007;
    }
    cout << answer << "\n";
}

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