Submission #1080139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080139		isaachew	Port Facility (JOI17_port_facility)	C++17	100 / 100	983 ms	271204 KiB

port_facility

#include <bits/stdc++.h>
/*
 Two stacks
 Ranges intersect -> not on the same stack
 Segtree and DSU
 
 Very similar to BOJ 7083
 */
bool possible;
int numccs;
std::vector<int> parents;
std::vector<int> states;
int find(int x){//parent, its state
    if(parents[x]==-1)return x;
    int fnd=find(parents[x]);
    if(fnd!=parents[x]){//fnd is the parent's parent
        states[x]^=states[parents[x]];
        parents[x]=fnd;
    }
    return fnd;
}
bool merge(int a,int b){//merging with opposite parity; returns false if cannot
    int fa=find(a);
    int fb=find(b);
    if(fa==fb){
        return states[a]!=states[b];
    }
    numccs--;
    states[fb]=states[b]^states[a]^1;
    parents[fb]=fa;
    return 1;
}

struct segtree{
    int size;
    std::vector<std::vector<int>> nodes;//it is cleared every time anyway
    segtree(int n){
        nodes.resize(2*n-1);
        size=n;
    }
    void add(int l,int r,int x,int nl,int nr,int ni){
        if(r<=nl||l>=nr)return;
        if(l<=nl&&r>=nr){
            nodes[ni].push_back(x);
            return;
        }
        int nm=(nl+nr)/2;
        add(l,r,x,nl,nm,ni+1);
        add(l,r,x,nm,nr,ni+2*(nm-nl));
    }
    void query(int pos,int val,int nl,int nr,int ni){
        if(pos<nl||pos>=nr)return;
        for(int i:nodes[ni]){
            possible&=merge(i,val);
        }
        if(nodes[ni].size()>1)nodes[ni].resize(1);//max looked at is 1 as everything was merged
        if(nl+1>=nr)return;
        int nm=(nl+nr)/2;
        query(pos,val,nl,nm,ni+1);
        query(pos,val,nm,nr,ni+2*(nm-nl));
    }
};
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int m;
    std::cin>>m;
    int n=2*m;
    numccs=m;
    std::vector<std::pair<int,int>> intervs;
    std::vector<int> sinds;
    for(int i=0;i<m;i++){
        sinds.push_back(i);
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        intervs.push_back({std::min(a,b),std::max(a,b)});
    }
    std::sort(sinds.begin(),sinds.end(),[&](int a,int b){return intervs[a].second<intervs[b].second;});

    parents.resize(m,-1);
    states.resize(m,0);
    segtree st(n);
    possible=true;
    for(int i=0;i<m;i++){
        st.query(intervs[sinds[i]].first,i,0,n,0);
        st.add(intervs[sinds[i]].first,intervs[sinds[i]].second,i,0,n,0);
        if(!possible)break;
    }
    long long curnum=1;
    long long squ=2;
    for(int i=numccs;i;){
        if(i&1){
            curnum*=squ;
            curnum%=1000000007;
        }
        squ*=squ;
        squ%=1000000007;
        i/=2;
    }
    std::cout<<(possible?curnum:0)<<'\n';
}

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