Submission #1227768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227768		minhpk	Port Facility (JOI17_port_facility)	C++20	100 / 100	303 ms	118508 KiB

port_facility

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
pair<int,int> z[2000005];
int id[2000005];
int par[2000005];
int sz[2000005];
int mod=1e9+7;
int col[2000005];
int color(int u){
    if (par[u]==u){
        return col[u];
    }
    return col[u]^color(par[u]);
}
int find(int u){
    if (par[u]==u){
        return u;
    }
    return find(par[u]);
}
void join(int x,int y){
    int rootx=find(x);
    int rooty=find(y);
   // cerr << rootx << " " << rooty << "\n";
    if (rootx==rooty){
        if (color(x)==color(y)){
           // cout << "ok" << "\n";
            cout << 0 << "\n";
            exit(0);
        }else{
            return;
        }
    }
    if (sz[rootx]<sz[rooty]){
        swap(rootx,rooty);
    }
    sz[rootx]+=sz[rooty];
    par[rooty]=rootx;
    if (color(x)==color(y)){
        col[rooty]=1-col[rooty];
    }
    // cerr << rootx << " " << rooty << "\n";
}
int sta[2000005];
int res=1;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> z[i].first >> z[i].second;
    }
    sort(z+1,z+1+a);
    for (int i=1;i<=a;i++){
         sta[z[i].first]=1;
         id[z[i].second]=id[z[i].first]=i;
    }
    stack<list<int>> st;
    for(int i=1;i<=a;i++){
         par[i]=i;
         sz[i]=1;
    }
    for (int i=1;i<=2*a;i++){
         if (sta[i]){
             st.push({});
             st.top().push_back(id[i]);
         }else{
             int pos=0;
             int loop=0;
             list<int> lst;
             while (true){
                  if (st.size() && st.top().back()==id[i]){
                      st.top().pop_back();
                      if (!st.top().size()){
                          st.pop();
                      }
                      break;
                  }
                //  cerr << "Joining " << id[i] << " vs " << st.top() << "\n";
                  join(id[i],st.top().back());

                  lst.splice(lst.begin(),st.top());
                  st.pop();
             }
             if (lst.size()){
                st.push({});
                st.top().splice(st.top().begin(),lst);
             }
         }
    }
    for (int i=1;i<=a;i++){
         if (par[i]==i){
             res=res*2%mod;
         }
    }
    cout << res << "\n";
    return 0;
}

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