제출 #1142752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142752		VMaksimoski008	Port Facility (JOI17_port_facility)	C++20	22 / 100	6096 ms	40260 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 maxn = 1e6 + 5;

bool ok = 1;
int col[maxn];
vector<int> G[maxn];

void dfs(int u, int c=1) {
    col[u] = c;
    for(int v : G[u]) {
        if(col[v] == col[u]) ok = 0;
        if(!col[v]) dfs(v, 3 - c);
    }
}

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

    int n; cin >> n;
    vector<ar<int, 2> > a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1];
    sort(a.begin()+1, a.end());

    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(a[j][0] < a[i][1] && a[i][1] < a[j][1]) {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }

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

    cout << (ok ? ans : 0) << '\n';
}

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