Submission #21302

#	Time	Username	Problem	Language	Result	Execution time	Memory
21302		Ushio	Port Facility (JOI17_port_facility)	C++14	100 / 100	1676 ms	143104 KiB

port_facility

#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <queue>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

const int MOD = (int) 1e9 + 7;

struct Segment {
    int l, r;
    Segment() = default;
    Segment(int _l, int _r):
        l(_l), r(_r) {}
};

class DSU {
public:
    DSU(int n): f(vector<int>(n)) {
        for (int i = 0; i < n; ++i) {
            f[i] = i;
        }
    }
    int& operator[](int x) {
        int y, p;
        for (y = x; y != f[y]; y = f[y]);
        for (; x != y; x = p) {
            p = f[x];
            f[x] = y;
        }
        return f[y];
    }
private:
    vector<int> f;
};

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<Segment> a(n + 1);
    vector<int> event(2 * n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].l >> a[i].r;
        event[a[i].l] = i;
        event[a[i].r] = -i;
    }
    DSU f(n + 1);
    vector<int> before(n + 1, -1), last(n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        last[i] = i;
    }
    vector<bool> erased(n + 1, false);
    vector<int> stk;
    vector<vector<int>> diffGraph(n + 1);
    for (int i = 1; i <= 2 * n; ++i) {
        if (event[i] > 0) {
            int e = event[i];
            stk.push_back(e);
        } else {
            int e = -event[i];
            if (before[e] != -1) {
                if (!erased[before[e]]) {
                    cout << "0\n";
                    return 0;
                }
            }
            int xp = f[e];
            if (stk.back() == xp) {
                if (e == xp) {
                    stk.pop_back();
                }
            } else {
                int prev = -1;
                while (!stk.empty() && stk.back() != xp) {
                    int x = stk.back();
                    stk.pop_back();
                    if (prev == -1) {
                        before[last[x]] = -1;
                    } else {
                        before[last[x]] = prev;
                        last[x] = last[prev];
                        f[prev] = x;
                    }
                    prev = x;
                }
                if (e == xp) {
                    stk.pop_back();
                }
                stk.push_back(prev);
                diffGraph[prev].push_back(e);
                diffGraph[e].push_back(prev);
            }
            erased[e] = true;
        }
    }
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i <= n; ++i) {
        for (int to: diffGraph[i]) {
            graph[f[i]].push_back(f[to]);
        }
    }
    vector<bool> used(n + 1, false);
    vector<int> color(n + 1);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (!used[i] && f[i] == i) {
            queue<int> q;
            q.push(i);
            used[i] = true;
            color[i] = 0;
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                for (int to: graph[node]) {
                    if (!used[to]) {
                        used[to] = true;
                        color[to] = color[node] ^ 1;
                        q.push(to);
                    }
                }
            }
            cnt++;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (f[i] != i) continue;
        for (int to: graph[i]) {
            if (color[i] == color[to]) {
                cnt = -1;
            }
        }
    }
    if (cnt == -1) {
        cout << "0\n";
    } else {
        int ans = 1;
        for (int i = 0; i < cnt; ++i) {
            ans = (ans + ans) % MOD;
        }
        cout << ans << '\n';
    }
}

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