Submission #996804

#	Time	Username	Problem	Language	Result	Execution time	Memory
996804		Sharky	Port Facility (JOI17_port_facility)	C++17	22 / 100	30 ms	4696 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9+7;

int p[4001], sz[4001], conn = 0, ans = 1;
set<int> disc;

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    p[v] = u, sz[u] += sz[v];
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= 2 * n; i++) p[i] = i, sz[i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (a[i] < a[j] && a[j] < b[i] && b[i] < b[j]) {
                merge(i, j + n);
                merge(i + n, j);
            }
        }
    }
    for (int i = 1; i <= n; i++) if (find(i) == find(i + n)) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i <= 2 * n; i++) {
        int x = find(i);
        if (x > n) x -= n;
        disc.insert(x);
    }
    conn = disc.size();
    for (int i = 1; i <= conn; i++) ans = ans * 2 % mod;
    cout << ans << '\n';
}

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