Submission #132109

#	Time	Username	Problem	Language	Result	Execution time	Memory
132109		shayan_p	Port Facility (JOI17_port_facility)	C++14	100 / 100	3332 ms	414816 KiB

port_facility

// only miss the sun when it starts to snow

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=2e6+10,mod=1e9+7;
const ll inf=1e18;

int par[maxn], who[maxn], n;
bool st[maxn], bad=0;
vector<int> v[4*maxn];

pair<int,bool> Find(int u){
    if(par[u]<0) return {u,0};
    pair<int,bool> a= Find(par[u]);
    a.S^= st[u];
    par[u]= a.F, st[u]= a.S;

    return {par[u],st[u]};
}
void Merge(int a,int b){
    if(a==b) return;
    pair<int,bool> A=Find(a), B=Find(b);

    if(A.F == B.F){
	bad|= A.S==B.S;
	return;
    }
    if( par[A.F] > par[B.F] ) swap(A,B);

    par[A.F]+=par[B.F];
    par[B.F]= A.F;
    st[B.F]= A.S ^ B.S ^ 1;
}

void build(int l=0,int r=maxn, int id=1){
    if(r-l==1){
	if(who[l] != 0)	v[id].PB( who[l] );
	return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*id);
    build(mid,r,2*id+1);
    v[id].resize( sz(v[2*id]) + sz(v[2*id+1]) );
    merge( v[2*id].begin(), v[2*id].end(), v[2*id+1].begin(), v[2*id+1].end(), v[id].begin() );
}
void mrg(int f,int s,int l=0,int r=maxn,int id=1){
    if(f>=s || l>=r|| s<=l || r<=f) return;
    if(f<=l && r<=s){
	int mx=-1;
	while(sz(v[id]) && s<v[id].back() ) Merge(v[id].back(), s), mx=max(mx, v[id].back() ), v[id].pop_back();
	if(mx!=-1) v[id].PB(mx);
	return;
    }
    int mid=(l+r)>>1;
    mrg(f,s,l,mid,2*id), mrg(f,s,mid,r,2*id+1);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    memset(par,-1,sizeof par);

    cin>>n;

    for(int i=0;i<n;i++){
	int a,b; cin>>a>>b;
	who[a]= b;
    }

    build();

    for(int i=1;i<=2*n;i++){
	if(who[i]!=0){
	    mrg(i,who[i]);
	}
    }
    if(bad) return cout<<0<<endl,0;

    set<int> st;

    for(int i=1;i<=2*n;i++){
	if(who[i]!=0){
	    st.insert(Find(who[i]).F);
	}
    }
    int ans=1;
    for(int i=0;i<sz(st);i++)
	ans=2ll*ans %mod;
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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