Submission #1225186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225186		salmon	Port Facility (JOI17_port_facility)	C++20	100 / 100	792 ms	220092 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

int N;
int lst[2100100];
int A[1100100];
int B[1100100];
int col[2100100];
vector<set<int>*> Bs;
vector<int> As;
vector<int> adjlst[2100100];
bool visited[2100100];
int mod = 1'000'000'007;

void dfs(int i, int c){
	col[i] = c;
	visited[i] = true;
	//printf("s");
	
	for(int j : adjlst[i]){
		if(!visited[j]) dfs(j,1-c);
	}
}

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 1; i <= N * 2; i++){
		lst[i] = -1;
		visited[i] = false;
	}
	
	for(int i = 0; i < N; i++){
		scanf(" %d",&A[i]);
		scanf(" %d",&B[i]);
		lst[A[i]] = B[i];
		lst[B[i]] = A[i];
	}

	int ways = 1;
	
	for(int i = 1; i <= N * 2; i++){ 
		if(Bs.empty()){
			Bs.push_back(new set({lst[i]}));
			As.push_back(i);
		}
		else if(lst[i] > i){
			//printf("v: %d\n",i);
			bool die = false;
			
			while(!Bs.empty() && !die){
				die = true;
				while(!(Bs.back() -> empty()) && *(Bs.back() -> begin()) <= i){
					//printf("poop %d\n",*(Bs.back() -> begin()));
					Bs.back() -> erase(Bs.back() -> begin());
					die = false;
				}

				if(Bs.back() -> empty()){
					ways = ways * 2 % mod;
					Bs.pop_back();
					As.pop_back();
				}
			}
			
			if(Bs.empty()){
				//printf("die %d\n",i);
				Bs.push_back(new set({lst[i]}));
				As.push_back(i);
				continue;
			}
			
				//printf("v: %d \n",i);
			if(!Bs.empty()){
				if(*(Bs.back() -> begin()) > lst[i]){
					Bs.push_back(new set({lst[i]}));
					As.push_back(i);
				}
				else{
					adjlst[i].push_back(lst[*(Bs.back() -> begin())]);
					adjlst[lst[*(Bs.back() -> begin())]].push_back(i);
					
					set<int>* s1 = Bs.back();
					
					s1 -> insert(lst[i]);
					
					Bs.pop_back();
					As.pop_back();
					
					while(!Bs.empty() && *(Bs.back() -> begin()) < lst[i]){
						adjlst[i].push_back(lst[*(Bs.back() -> begin())]);
						adjlst[lst[*(Bs.back() -> begin())]].push_back(i);
						
						set<int>* s2 = Bs.back();
						
						if(s1 -> size() < s2 -> size()) swap(s1,s2);
						
						for(int i : (*s2)) s1 -> insert(i);
						
						Bs.pop_back();
						As.pop_back();
					}
					
					As.push_back(i);
					Bs.push_back({});
					swap(Bs.back(),s1);
				}
			}
			
		}
	}

	for(set<int>* _ : Bs)ways = ways *  2 % mod;
	
	for(int i = 1; i <= N * 2; i++){
		//printf("i: %d ",i);
		//for(int j : adjlst[i]) printf("%d ",j);
		//printf("\n");
		if(!visited[i] && lst[i] > i) dfs(i,0);
	}
	
	vector<int> s1;
	vector<int> s2;
	
	bool contra = false;
	
	for(int i = 1; i <= N * 2; i++){
		if(lst[i] > i){
			if(col[i] == 0) s1.push_back(lst[i]);
			else s2.push_back(lst[i]);
		}
		else{
			if(s1.back() == i) s1.pop_back();
			else if(s2.back() == i) s2.pop_back();
			else contra = true;
		}
	}
	
	if(contra){
		printf("0\n");
		return 0;
	}
	
	printf("%d\n",ways);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
port_facility.cpp:35:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |                 scanf(" %d",&A[i]);
      |                 ~~~~~^~~~~~~~~~~~~
port_facility.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |                 scanf(" %d",&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~

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