Submission #22953

#	Time	Username	Problem	Language	Result	Execution time	Memory
22953		sbansalcs	Port Facility (JOI17_port_facility)	C++14	0 / 100	33 ms	226636 KiB

port_facility

#include <iostream>
#include <vector>
#include <set>
#include <assert.h>
using namespace std;
const int N = 1e6+5;

set<int> st[N][2];
set<int> st2[N][2];

int A[N],B[N];
pair<int,int> arr[N];
int comps;
bool in[2*N];
int ver[2*N];
int rel[N];
int parent[N];
int sz[N];
set<int> ms;
int read()	{
	int x;return scanf("%d",&x),x;
}

bool addE(int a, int b)	{
	// cout<<"addE : "<<a<<" "<<b<<endl;	
	int u = parent[a],v=parent[b];
	// cout<<"oh : "<<u<<"  "<<v<<endl;
	if(u==v)	{
		return rel[a]!=rel[b];
	}
	comps--;
	int d = !(rel[a]^rel[b]);
	if(sz[a]>sz[b])	swap(a,b);
	for(int i=0;i<2;i++)	{
		for(auto c:st[a][i])	{
			st[b][i^d].insert(c);
			st2[b][i^d].insert(B[c]);
			parent[c]=b;
			rel[c]^=d;

		}
	}
	return 1;
}

int get_replacement(int x, int a)	{
	int p = parent[x];
	int d = rel[x];
	set<int>::iterator it; 
	it = st2[p][d].lower_bound(a+1);
	if(it!=st2[p][d].end())	return *it;
	return -1;
}

int main()	{
	int n=read();
	comps=n;
	for(int i=1;i<=n;i++)	{
		A[i]=read();B[i]=read();
		in[A[i]]=1;
		ver[A[i]]=ver[B[i]]=i;
		parent[i]=i;
		st[i][0].insert(i);
		sz[i]=1;
		st2[i][0].insert(B[i]);
	}
	for(int i=1;i<=2*N;i++)	{
		if(!in[i])	continue;
		int v = ver[i];
		vector<int> vt;
		for(auto c:ms)	{
			if(c>A[v])	break;
			vt.push_back(c);
		}
		for(auto c:vt)	{
			assert(c<A[v]);
			int h = get_replacement(ver[c],A[v]);
			assert(h>A[v] || h==-1);

			// cout<<"erased : "<<c<<"  and inserted: "<<h<<endl;
			ms.erase(ms.find(c));
			if(h!=-1)	ms.insert(h);
		}
		bool f=0;
		vt.clear();
		for(auto c:ms)	{
			if(c>B[v])	break;
			if(!addE(v,ver[c]))	{
				// cout<<"fuck : "<<v<<" "<<c<<" "<<ver[c]<<endl;
				cout<<0;return 0;
			}
			if(f==0)	f=1;
			else	vt.push_back(c);
		}
		for(auto c:vt)	{
			ms.erase(ms.find(c));
		}
		ms.insert(B[v]);

	}
	// cout<<"yeah : \n";
	// cout<<comps<<endl;
	long long ans=1;int mod=1e9+7;
	for(int i=1;i<=comps;i++)	{
		ans=(ans*2)%mod;
	}
	cout<<ans;
	
}

Compilation message (stderr)

port_facility.cpp: In function 'int read()':
port_facility.cpp:21:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int x;return scanf("%d",&x),x;
                              ^

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