Submission #427128

#	Time	Username	Problem	Language	Result	Execution time	Memory
427128		kai824	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	332 KiB

port_facility

#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=1;i<=n;i++){
    cin>>a>>b;
    eve[a]=i;
    eve[b]=-i;
    sz[i]=1;par[i]=-1;
  }
  vector<int> st;
  for(int i=1;i<=n+n;i++){
    if(eve[i]>0)st.push_back(eve[i]);
    else{
      for(int j=st.size()-1;j>=0;j--){
        if(st[j]==-eve[i]){
          st.erase(st.begin()+j);
          break;
        }
        merge(st[j],-eve[i]);
      }
    }
    //for(int x:st)cout<<x<<' ';cout<<'\n';
  }
  if(bruh)cout<<0;
  else{
    int ans=1;
    for(int i=1;i<=n;i++){
      if(par[i]==-1){
        ans<<=1;
        ans%=1000000007ll;
      }
    }
    cout<<ans;
  }
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22