Submission #832512

#TimeUsernameProblemLanguageResultExecution timeMemory
832512LucaIliePort Facility (JOI17_port_facility)C++17
22 / 100
6063 ms40032 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e6; const int MOD = 1e9 + 7; bool vis[MAX_N], side[MAX_N]; int l[MAX_N], r[MAX_N]; vector<int> edges[MAX_N]; bool bipartit = true; void checkBipartit( int u ) { vis[u] = true; for ( int v: edges[u] ) { if ( vis[v] ) { if ( side[u] == side[v] ) bipartit = false; } else { side[v] = side[u] ^ 1; checkBipartit( v ); } } } int main() { int n; cin >> n; for ( int i = 0; i < n; i++ ) cin >> l[i] >> r[i]; for ( int i = 0; i < n; i++ ) { for ( int j = i + 1; j < n; j++ ) { if ( (l[i] <= l[j] && r[i] <= r[j] && r[i] >= l[j]) || (l[j] <= l[i] && r[j] <= r[i] && r[j] >= l[i]) ) { edges[i].push_back( j ); edges[j].push_back( i ); } } } int comp = 0; for ( int u = 0; u < n; u++ ) { if ( !vis[u] ) { side[u] = 0; checkBipartit( u ); comp++; } } if ( bipartit ) { int ans = 1; for ( int i = 0; i < comp; i++ ) ans = ans * 2 % MOD; cout << ans; } else cout << 0; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...