# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
44587 | ffresh | Port Facility (JOI17_port_facility) | C++17 | 6090 ms | 5112 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+15,mod = 1e9+7;
int L[N],R[N];
int par[N],enemy[N];
int find(int a){
if(a==-1)return -1;
if(a==par[a])return a;
return par[a]= find(par[a]);
}
void make_enemy(int a,int b){
a = find(a),b = find(b);
int u = find(enemy[a]), v = find(enemy[b]);
if(a==b || (u!=-1 && u==v)){
printf("0\n");
exit(0);
}
if(v!=-1)par[v]= a;
if(u!=-1)par[u]= b;
enemy[a]= b;
enemy[b]= a;
}
int check(int a,int b){
int x = (L[a]<R[b] && R[b]<R[a]);
int y= (L[a]<L[b] && L[b]<R[a]);
if( (x+y)%2==1)return 1;
return 0;
}
int main(){
//freopen("input.txt","r",stdin);
int n;
cin>>n;
vector<pair<int,int> >v;
for(int i=1;i<=n;++i){
scanf("%d%d",&L[i],&R[i]);
v.push_back(make_pair(L[i],i));
}
sort(v.begin(),v.end());
for(int i=1;i<=n;++i)par[i]= i,enemy[i]= -1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j){
if(check(i,j))
make_enemy(i,j);
}
long long ret= 1;
for(int i=1;i<=n;++i){
if(find(i)==i&& find(enemy[i])<i){
ret= (ret*2)%mod;
}
}
cout<<ret<<endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |