Submission #1264204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264204		lambd47	Port Facility (JOI17_port_facility)	C++20	10 / 100	1 ms	580 KiB

port_facility

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n;cin>>n;
    vector<int> pai(n);
    iota(all(pai),0);

    vector<int> ev(2*n);
    vector<int> ini(n);
    L(i,0,n-1){
        int a,b;cin>>a>>b;a--;b--;
        ev[a]=i;
        ev[b]=i;
        ini[i]=a;
    }

    vector<int> muda(n,0);
    vector<int> tam(n,1);
    auto find=[&](auto&& self, int node)->int{
        if(node==pai[node])return node;
        int x=self(self,pai[node]);
        muda[node]^=muda[pai[node]];
        return x;
    };
    auto uni=[&](int a, int b)->bool{
        int x=a;int y=b;
        a=find(find,a);
        b=find(find,b);
        if(a==b){
            if(muda[x]==muda[y])return false;
            return true;
        }
        if(tam[a]<tam[b])swap(a,b);
        pai[b]=a;
        muda[b]=(muda[x]==muda[y])?1:0;
        tam[a]+=tam[b];
        return true;
    };


    set<pair<int,int>> ativo;
    L(i,0,2*n-1){
        int at=ev[i];
        if(ativo.find({ini[at],at})==ativo.end()){
            ativo.insert({ini[at],at});
        }
        else{
            ativo.erase({ini[at],at});
            auto pt=ativo.lower_bound({ini[at],0});
            while(pt!=ativo.end()){
                int a=(*pt).second;
                if(!uni(at,a)){
                  cout<<0<<"\n";return;
                }
                pt++;
            }
        }
    }
    vector<int> ehp(n,0);
    L(i,0,n-1){
        ehp[find(find,i)]=1;
    }
    const int MOD=1e9+7;
    int resp=1;
    L(i,0,n-1){
        if(ehp[i]){
            resp*=2;
            resp%=MOD;
        }
    }
    cout<<resp<<"\n";return;



}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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