제출 #996804

#제출 시각아이디문제언어결과실행 시간메모리
996804SharkyPort Facility (JOI17_port_facility)C++17
22 / 100
30 ms4696 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9+7; int p[4001], sz[4001], conn = 0, ans = 1; set<int> disc; int find(int u) { return p[u] == u ? u : p[u] = find(p[u]); } void merge(int u, int v) { u = find(u), v = find(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); p[v] = u, sz[u] += sz[v]; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n+1), b(n+1); for (int i = 1; i <= n; i++) cin >> a[i] >> b[i]; for (int i = 1; i <= 2 * n; i++) p[i] = i, sz[i] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; if (a[i] < a[j] && a[j] < b[i] && b[i] < b[j]) { merge(i, j + n); merge(i + n, j); } } } for (int i = 1; i <= n; i++) if (find(i) == find(i + n)) { cout << "0\n"; return 0; } for (int i = 1; i <= 2 * n; i++) { int x = find(i); if (x > n) x -= n; disc.insert(x); } conn = disc.size(); for (int i = 1; i <= conn; i++) ans = ans * 2 % mod; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...