Submission #1255197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255197		wedonttalkanymore	Port Facility (JOI17_port_facility)	C++20	22 / 100	6093 ms	37444 KiB

port_facility

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

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, mod = 1e9 + 7;

int n;
pii a[N];
vector<int> adj[N];
int color[N], vst[N];

int power(int a, int b) {
    if (b == 0) return 1;
    int t = power(a, b / 2);
    t = (t * t) % mod;
    if (b % 2) t = (t * a) % mod;
    return t;
}

void dfs(int u) {
    vst[u] = 1;
    for (int v : adj[u]) {
        if (!vst[v]) {
            color[v] = color[u] ^ 1;
            dfs(v);
        }
        else if (color[v] == color[u]) {
            cout << 0;
            exit(0);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1);
    // cout << a[1].fi << ' ' << a[1].se << '\n';
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            ll l1 = a[i].fi, r1 = a[i].se;
            ll l2 = a[j].fi, r2 = a[j].se;
            // cout << i << ' ' << l1 << ' ' <<  r1 << ' ' << l2 << ' ' << r2 << '\n';
            if ((l1 < l2 && l2 < r1 && r1 < r2) ||
                (l2 < l1 && l1 < r2 && r2 < r1)) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << "now: " << i << '\n';
    //     for (auto v : adj[i]) cout << v << ' ';
    //     cout << '\n';
    // }
    int comp = 0;
    for (int i = 1; i <= n; i++) {
        if (!vst[i]) {
            comp++;
            dfs(i);
        }
    }
    cout << power(2, comp);
    return 0;
}

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