이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 2000;
const int MOD = (int) 1e9 + 7;
int N;
int L[N_MAX + 2], R[N_MAX + 2];
vector <int> adj[N_MAX + 2];
int color[N_MAX + 2];
void dfs (int u) {
for (int v : adj[u]) {
if (color[v] == 0) {
color[v] = 3 - color[u];
dfs(v);
} else if (color[v] != 3 - color[u]) {
cout << 0 << "\n";
exit(0);
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> L[i] >> R[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (L[i] < L[j] && L[j] < R[i] && R[i] < R[j]) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
int answer = 1;
for (int i = 1; i <= N; i++) {
if (color[i] == 0) {
color[i] = 1;
dfs(i);
answer = answer * 2 % MOD;
}
}
cout << answer << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |