Submission #22975

#	Time	Username	Problem	Language	Result	Execution time	Memory
22975		sbansalcs	Port Facility (JOI17_port_facility)	C++14	22 / 100	3500 ms	61852 KiB

port_facility

	#include <iostream>
	#include <vector>
	#include <set>
	#include <assert.h>
	using namespace std;
	const int N = 2e5+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 vt[N];
	int done[2*N];
	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[u]>sz[v])	swap(u,v);
		for(int i=0;i<2;i++)	{
			for(auto c:st[u][i])	{
				st[v][i^d].insert(c);
				st2[v][i^d].insert(B[c]);
				parent[c]=v;
				rel[c]^=d;

			}
		}
		st[u][0].clear();
		st[u][1].clear();

		st2[u][0].clear();
		st2[u][1].clear();

		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;
	}

	void ass(bool x)	{
		while(!x)	{

		}
	}

	int main()	{
		int ss=0;
		int n=read();
		comps=n;
		int dd=0;
		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]);
		}
					// vector<int> vt;
		int v;
		for(int i=1;i<=2*n;i++)	{
			if(!in[i])	continue;
			// vt.clear();
			ss=0;
			 v = ver[i];
			ass(A[v]==i);
			for(auto c:ms)	{
				if(c>A[v])	break;
				// vt.push_back(c);
				vt[++ss]=c;
			}
			int c;
			for(int j=1;j<=ss;j++)	{
				c= vt[j];
				// assert(c<A[v]);
				// assert(c!=A[v]);
				// while(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),dd++;
							assert(dd<=N*10);

			}
			bool f=0;
			ss=0;
			for(auto c:ms)	{
				if(c>B[v])	break;
				if(!addE(v,ver[c]))	{
					// cout<<"fuck : "<<v<<" "<<c<<" "<<ver[c]<<endl;
					// assert(0);
					cout<<0;return 0;
				}
				if(f==0)	f=1;
				else	vt[++ss]=c;
			}

			for(int j=1;j<=ss;j++)	{
				c= vt[j];
				ms.erase(ms.find(c));
			}
			ms.insert(B[v]);dd++;
			assert(dd<=N*10);

		}
		// 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;
		
		return 0;
	}

Compilation message (stderr)

port_facility.cpp: In function 'int read()':
port_facility.cpp:23:31: 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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22