제출 #1223250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223250		rythm_of_knight	Port Facility (JOI17_port_facility)	C++17	0 / 100	11 ms	23872 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];

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;
    g[sa].push_back(sb);
    g[sb].push_back(sa);
    if (sz[a] < sz[b])
        swap(a, b);
    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;
    vector <int> p(m + 1, -1), w(m + 1);
    for (int i = 1; i <= n; i++) {
        f[i] = i, sz[i] = 1;
        int a, b;
        cin >> a >> b;
        p[a] = 0;
        p[b] = a;
        w[a] = w[b] = i;
    }
    stack <int> pos;
    for (int cur = 1; cur <= m; cur++) {
        if (!p[cur]) {
            pos.push(cur);
        } else {
            while (!pos.empty() && pos.top() >= p[cur]) {
                dsu(w[pos.top()], w[cur]);
                pos.pop();
            }
        }
    }
    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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22