제출 #999334

#제출 시각아이디문제언어결과실행 시간메모리
999334AdamGSPort Facility (JOI17_port_facility)C++17
22 / 100
6100 ms56700 KiB
#include<bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const ll MOD=1e9+7; const int LIM=1e6+7; vector<int>V[LIM]; ll ans=1; pair<int,int>T[LIM]; int kol[LIM]; void DFS(int x, int o) { for(auto i : V[x]) { if(!kol[i]) { kol[i]=kol[x]^3; DFS(i, x); } else if(kol[i]==kol[x]) ans=0; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; rep(i, n) cin >> T[i].st >> T[i].nd; sort(T, T+n); rep(i, n) rep(j, i) if(T[j].st<T[i].st && T[i].st<T[j].nd && T[j].nd<T[i].nd) { V[i].pb(j); V[j].pb(i); } rep(i, n) if(!kol[i]) { kol[i]=1; DFS(i, 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...