Submission #540427

#	Time	Username	Problem	Language	Result	Execution time	Memory
540427		Berted	Port Facility (JOI17_port_facility)	C++14	0 / 100	26 ms	47324 KiB

port_facility

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

const int MD = 1e9 + 7;

int T, N, cnt, A[2000001], par[2000001], pos[2000001];
vector<int> mem[2000001];
int color[2000001] = {}, mx[2000001][2][2];
set<int> S;

int find(int x) {return (x == par[x]) ? x : find(par[x]);}
inline bool join(int a, int b) {
    int ka = color[a], kb = color[b];
    //cerr << "JOIN: " << a << " " << b << " called\n";
    a = find(a), b = find(b);
    if (a == b) return ka != kb;
    else {
        cnt--;
        if (mem[a].size() < mem[b].size()) swap(a, b);
        par[b] = a;
        while (mem[b].size()) {
            mem[a].push_back(mem[b].back());
            color[mem[b].back()] ^= (ka == kb);
            mem[b].pop_back();
        }
        for (int i = 0; i < 2; i++) {
            vector<int> temp = {mx[a][i][0], mx[a][i][1], mx[b][i ^ (ka == kb)][0], mx[b][i ^ (ka == kb)][1]};
            sort(temp.begin(), temp.end());
            mx[a][i][0] = temp[3];
            mx[a][i][1] = temp[2];
        }
        //cerr << b << " now rooted to " << a << "\n";
        return 1;
    }
}

int main() {

    ios :: sync_with_stdio(0); cin.tie(0);
    bool yes = true;

    cin >> N;
    cnt = N;

    S.clear();
    for (int i = 0; i < N; i++) {
        pos[i] = -1;
        par[i] = i;
        color[i] = 0;
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++) mx[i][j][k] = -1;
        mem[i] = {i};
    }

    for (int i = 0; i < N; i++) {
        int a, b; cin >> a >> b;
        A[a - 1] = i; A[b - 1] = i;
    }

    for (int i = 0; i < 2 * N; i++) {
        int u; u = A[i];
        if (pos[u] == -1) {
            //cerr << "IS: " << i << "\n";
            S.insert(i);
            pos[u] = i;
        } else if (pos[u] != -2) {
            auto it = S.upper_bound(pos[u]);
            while (it != S.end()) {
                int v = *it, vv = A[v];
                yes &= join(vv, u);
                //cerr << "Check: " << vv << " " << v << " " << find(vv) << " " << color[vv] << "\n";
                if (v < mx[find(vv)][color[vv]][1]) it = S.erase(it);
                else {it++;}
            }
            S.erase(pos[u]);
            pos[u] = -2;
        } else {
            yes = false;
            break;
        }

        mx[find(u)][color[u]][1] = mx[find(u)][color[u]][0];
        mx[find(u)][color[u]][0] = i;
    }

    if (yes) {
        int res = 1;
        for (int i = 0; i < cnt; i++) {
            res = res << 1;
            if (res >= MD) res -= MD;
        }
        cout << res << "\n";
    } else {cout << "0\n";}

    return 0;
}

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