Submission #79453

#	Time	Username	Problem	Language	Result	Execution time	Memory
79453		Plurm	Port Facility (JOI17_port_facility)	C++11	22 / 100	6093 ms	38284 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
vector<int> g[1000005];
int col[1000005];
bool dfs(int u,int p = -1,int c = 1){
	col[u] = c;
	c = c % 2 + 1;
	for(int v : g[u]){
		if(v == p) continue;
		if(col[v] && col[v] != c) return false;
		if(col[v]) continue;
		if(!dfs(v,u,c)) return false;
	}
	return true;
}
int main(){
	int n;
	scanf("%d",&n);
	vector<pair<int,int> > pts;
	int a,b;
	for(int i = 0; i < n; i++){
		scanf("%d%d",&a,&b);
		pts.emplace_back(a,b);
	}
	sort(pts.begin(),pts.end());
	for(int i = 0; i < n; i++){
		int bc = 0;
		pair<int,int> x,y;
		for(int j = i+1; j < n && pts[j].first < pts[i].second; j++){
			if(pts[i].second < pts[j].second){
				if(bc == 0) x = pts[j];
				else y = pts[j];
				g[j].push_back(i);
				g[i].push_back(j);
				bc++;
			}
			if(bc == 2 && x.first < y.first && y.first < x.second && x.second < y.second){
				printf("0\n");
				return 0;
			}
		}
	}
	int c = 0;
	for(int i = 0; i < n; i++){
		if(!col[i]){
			if(dfs(i)) c++;
			else{
				printf("0\n");
				return 0;
			}
		}
	}
	int ans = 1;
	for(int i = 0; i < c; i++){
		ans *= 2;
		ans %= 1000000007;
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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