Submission #113624

#TimeUsernameProblemLanguageResultExecution timeMemory
113624aminraPort Facility (JOI17_port_facility)C++14
22 / 100
6012 ms63708 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int MOD = (int)1e9 + 7; const int MAXN = (int)2e6 + 3; const int infint = (int)2e9; const ll inf = (ll)2e18; int cyc = 0; int a[MAXN], b[MAXN], n, c[MAXN]; vector<int> G[MAXN]; void dfs(int u, int color) { c[u] = color; for (auto v : G[u]) if(!c[v]) dfs(v, 3 - color); else if(c[v] == c[u]) cyc = 1; } int pwr(int a, int b) { if(b == 0) return 1; int c = pwr(a, b >> 1); c = 1LL * c * c % MOD; if(b & 1) c = 1LL * c * a % MOD; return c; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if((a[i] < a[j] && a[j] < b[i] && b[j] > b[i]) || (a[j] < a[i] && a[i] < b[j] && b[i] > b[j])) G[i].push_back(j), G[j].push_back(i); int sz = 0; for (int i = 0; i < n; i++) if(!c[i]) dfs(i, 1), sz++; if(cyc) return cout << 0, 0; cout << pwr(2, sz); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...