Submission #1213865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213865		VMaksimoski008	Port Facility (JOI17_port_facility)	C++20	0 / 100	11 ms	23880 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;   
    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]) {
                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;
    }

    int cyc = 1e9;
    for(int i=1; i<=1; i++) {
        queue<pii> q;
        q.push({ 1, 1 });
        vector<int> d(n+1, 1e9);
        d[1] = 0;

        while(!q.empty()) {
            auto [u, p] = q.front(); q.pop();
            for(int v : g[u]) {
                if(d[v] == 1e9) {
                    d[v] = d[u] + 1;
                    q.push({ v, u});
                } else {
                    // cout << i << " " << u << " " << v << endl;
                    if(v != p && (d[u] + d[v] + 1) % 2 == 1)
                        cyc = min(cyc, d[u] + d[v] + 1);
                }
            }
        }
    }

    if(cyc == 1e9) cyc = 0;
    // cout << cyc << endl;
    assert(cyc <= 3);
    cout << ans << '\n';
}

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