제출 #1223307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223307		rythm_of_knight	Port Facility (JOI17_port_facility)	C++17	100 / 100	1220 ms	181988 KiB

port_facility

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e6 + 6, mod = 1e9 + 7;
vector <int> g[N];
int f[N], sz[N], d[N], done[N], w[N << 1], p[N << 1];
set <int> nxt;
priority_queue <int> tp[N];

int father(int x) {
    if (f[x] != f[f[x]])
        return f[x] = father(f[x]);
    return f[x];
}

void dsu(int a, int b) {
    int sa = a, sb = b;
    a = father(a), b = father(b);
    if (a == b)
        return;
    // cout << sa << ' ' << sb << '\n' << flush;
    g[sa].push_back(sb);
    g[sb].push_back(sa);
    if (sz[a] < sz[b])
        swap(a, b);
    if (!tp[b].empty() && !tp[a].empty()) {
        int tpa = tp[a].top(), tpb = tp[b].top();
        if (tpa < tpb)
            nxt.erase(-tpa);
        else
            nxt.erase(-tpb);
    }
    while (!tp[b].empty()) {
        tp[a].push(tp[b].top());
        tp[b].pop();
    }
    f[b] = a;
    sz[a] += sz[b];
}

void dfs(int x, int par) {
    d[x] = d[par] + 1;
    for (int y : g[x])
        if (y != par)
            dfs(y, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int m = n << 1;
    for (int i = 1; i <= n; i++) {
        f[i] = i, sz[i] = 1;
        int a, b;
        // cout << i << ": " << flush;
        cin >> a >> b;
        tp[i].push(a);
        p[a] = 0;
        p[b] = a;
        w[a] = w[b] = i;
    }
    for (int cur = 1; cur <= m; cur++) {
        if (!p[cur]) {
            nxt.insert(-cur);
        } else {
            int nd = - m - 1;
            while (!nxt.empty()) {
                auto nw = *nxt.upper_bound(nd);
                nw *= -1;
                if (nw <= p[cur])
                    break;
                dsu(w[nw], w[cur]);
                nd = -nw;
            }
            done[w[cur]] = 1;
            int par = father(w[cur]);
            if (tp[par].top() == p[cur]) {
                nxt.erase(-p[cur]);
                tp[par].pop();
            }
            while (!tp[par].empty() && done[w[tp[par].top()]])
                tp[par].pop();
            if (!tp[par].empty())
                nxt.insert(-tp[par].top());
        }
    }
    int com = 0;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            dfs(i, 0);
            com++;
        }
    }
    vector <int> ps[2];
    for (int i = 1; i <= m; i++) {
        if (!p[i]) {
            ps[d[w[i]] & 1].push_back(i);
        } else {
            int b = d[w[i]] & 1;
            if (!ps[b].empty() && ps[b].back() > p[i])
                return cout << 0, 0;
            ps[b].pop_back();
        }
    }
    int ans = 1;
    for (int i = 1; i <= com; i++)
        (ans <<= 1) %= mod;
    cout << ans;
}

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