Submission #1062299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062299		vjudge1	Port Facility (JOI17_port_facility)	C++17	22 / 100	33 ms	33564 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
ll pw[2000002];
int col[2020], l[2020], r[2020];
vector<int> adj[2020];
bool dfs(int v, int c = 1) {
    if (col[v]) return c == col[v];
    col[v] = c;
    for (auto& x : adj[v]) {
        if (!dfs(x, 3 - c)) return false;
    }
    return true;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    pw[0] = 1;
    for (int i = 1;i <= 2000000;i++) pw[i] = pw[i - 1] * 2 % MOD;
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> l[i] >> r[i];
    }
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            int ii = i, jj = j;
            if (l[i] > l[j]) swap(ii, jj);
            if (l[jj] < r[ii] && r[ii] < r[jj]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        if (!col[i]) {
            cnt++;
            if (!dfs(i)) {
                cout << 0 << '\n';
                return 0;
            }
        }
    }
    cout << pw[cnt] << '\n';
    return 0;
}

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