제출 #1155876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155876		anmattroi	Port Facility (JOI17_port_facility)	C++17	22 / 100	6091 ms	40004 KiB

port_facility

#include <bits/stdc++.h>
#define maxn 1000005
#define fi first
#define se second

using namespace std;
using ii = pair<int, int>;

constexpr int mod = 1000000007;

int n;
ii a[maxn];
vector<int> adj[maxn];
int cl[maxn];

void dfs(int u) {
    for (int v : adj[u])
    if (!cl[v]) {
        cl[v] = 3 - cl[u];
        dfs(v);
    } else if (cl[v] == cl[u]) {cout << 0; exit(0);}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++) if (a[i].se > a[j].fi && a[i].se < a[j].se) {
            adj[i].emplace_back(j);
            adj[j].emplace_back(i);
        }

    int slt = 0;
    for (int i = 1; i <= n; i++) if (!cl[i]) {
        ++slt;
        cl[i] = 1;
        dfs(i);
    }
    int ans = 1;
    while (slt--) ans = ans * 2 % mod;
    cout << ans;
}

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