Submission #1213896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213896		VMaksimoski008	Port Facility (JOI17_port_facility)	C++20	10 / 100	29 ms	24388 KiB

port_facility

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e6 + 5;

ll ans = 1;
int n, col[N], l[N], r[N];
vector<int> g[N];

void dfs(int u, int c) {
    col[u] = c;
    for(int v : g[u]) {
        if(col[v]) {
            if(col[v] == c) ans = 0;
            continue;
        }
        dfs(v, 3^c);
    }
}

signed main() {
    cin >> n;   
    int cnt = 0;
    for(int i=1; i<=n; i++) cin >> l[i] >> r[i];

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(l[i] < l[j] && r[i] < r[j] && l[j] < r[i]) {
                cnt++;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    for(int i=1; i<=n; i++) {
        if(col[i]) continue;
        dfs(i, 1);
        ans = ans * 2 % mod;
    }

    assert(cnt <= 20*n);
    cout << ans << '\n';
}

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