Submission #45563

#	Time	Username	Problem	Language	Result	Execution time	Memory
45563		qoo2p5	Port Facility (JOI17_port_facility)	C++17	22 / 100	6010 ms	27844 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = (int) 1e6 + 123;
const ll MOD = (ll) 1e9 + 7;

int n;
int a[N], b[N];
vector<int> g[N];
int col[N];

void dfs(int v, int cc = 1) {
    col[v] = cc;
    rep(u, 0, n) {
        if (!((a[u] < a[v] && a[v] < b[u] && b[u] < b[v]) || (a[v] < a[u] && a[u] < b[v] && b[v] < b[u]))) {
            continue;
        }
        if (!col[u]) {
            dfs(u, 3 - cc);
        }
        if (col[u] != 3 - cc) {
            cout << "0\n";
            exit(0);
        }
    }
}

void run() {
    cin >> n;
    rep(i, 0, n) {
        cin >> a[i] >> b[i];
    }
    
    ll ans = 1;
    
    rep(i, 0, n) {
        if (!col[i]) {
            dfs(i);
            ans *= 2;
            ans %= MOD;
        }
    }
    
    cout << ans << "\n";
}

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