이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
//shouldn't need, just in case...
int eve[2000005];
list<list<int> > luol;
list<int> tmp;
int par[1000005],sz[1000005];
int getr(int x){
if(par[x]==-1)return x;
return par[x]=getr(par[x]);
}
bool bruh=false;
void merge(int a,int b){
//cout<<"MERGE"<<a<<' '<<b<<'\n';
a=getr(a);b=getr(b);
if(a==b){
//cout<<"path1\n";
bruh=true;
return;
}
if(sz[a]<sz[b])swap(a,b);
par[b]=a;
sz[a]+=sz[b];
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int n;
cin>>n;
int a,b;
for(int i=0;i<n;i++){
cin>>a>>b;
eve[a]=(i+1);
eve[b]=-(i+1);
par[i+1]=-1;sz[i+1]=i;
}
for(int i=1;i<=(n*2);i++){
if(eve[i]>0){
luol.push_back(*(new list<int>));
luol.back().push_back(eve[i]);
}else{
eve[i]=-eve[i];
tmp= *(new list<int>);
while(true){
if(luol.size()==0){
//cout<<"path 2\n";
goto hell;
}
if(luol.back().back()==eve[i]){
luol.back().pop_back();
if(luol.back().size()==0)luol.pop_back();
break;
}
merge(eve[i],luol.back().back());
if(bruh)goto hell;
tmp.splice(tmp.begin(),luol.back());
luol.pop_back();
}
if(tmp.size()>0)luol.push_back(tmp);
}
/*for(auto x:luol){
for(auto y:x)cout<<y<<' ';cout<<'\t';
}cout<<'\n';*/
}
if(false){
hell:;
cout<<"0\n";
return 0;
}
int ans=1;
for(int i=1;i<=n;i++){
if(par[i]==-1){
ans*=2;
ans%=1000000007;
}
}
cout<<ans<<'\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... |