Submission #1226502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226502		duckindog	Port Facility (JOI17_port_facility)	C++20	0 / 100	2 ms	4160 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) { return id[u] < 0 ? u : root(id[u]); }
    int color(int u) { return id[u] < 0 ? c[u] : c[u] ^ color(id[u]); }
    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 color(u) ^ color(v);
        id[rootU] += id[rootV];
        id[rootV] = rootU;

        if (c[rootU] == c[rootV]) c[rootV] ^= 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<vector<int>> st;
    for (int i = 1; i <= 2 * n; ++i) { 
        if (type[i]) st.push({id[i]});
        else { 
            vector<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.insert(vt.end(), st.top().begin(), st.top().end());
                st.pop();
            }
            reverse(vt.begin(), vt.end());
            if (vt.size()) st.push(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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22