Submission #226800

#	Time	Username	Problem	Language	Result	Execution time	Memory
226800		tushar_2658	Port Facility (JOI17_port_facility)	C++14	22 / 100	43 ms	16512 KiB

port_facility

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

const int maxn = 2005;
using ll = long long;
ll mod = 1e9 + 7;

vector<int> edges[maxn];
pair<int, int> p[maxn];
int col[maxn];
int cnt = 0;

ll bigmod(ll a, ll b){
	if(b == 0)return 1;
	if(b & 1){
		ll ret = bigmod(a, b - 1);
		return (ret * a) % mod;
	}else {
		ll ret = bigmod(a, b / 2);
		return (ret * ret) % mod;
	}
}

bool bfs(int s){
	col[s] = 1;
	queue<int> q;
	q.push(s);
	++cnt;
	while(!q.empty()){
		s = q.front();
		q.pop();
		for(auto i : edges[s]){
			int x = 1;
			if(col[s] == 1)x = 2;
			if(col[i] == 0){
				col[i] = x;
				q.push(i);
			}else if(col[i] != x){
				return 0;
			}
		}
	}
	return 1;
}

int main(int argc, char const *argv[])
{
//	freopen("in.txt", "r", stdin); 
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		scanf("%d %d", &p[i].first, &p[i].second);
	}
	sort(p + 1, p + n + 1);
	for(int i = 1; i <= n; ++i){
		for(int j = i + 1; j <= n; ++j){
			if(p[j].first < p[i].second && p[j].second > p[i].second){
				edges[i].push_back(j);
				edges[j].push_back(i);
			}
		}
	}
	bool good = 1;
	for(int i = 1; i <= n; ++i){
		if(col[i] == 0){
			if(bfs(i) == 0){
				good = 0;
			}
		}
	}
	if(good == 0){
		printf("0\n");
		return 0;
	}
	printf("%lld\n", bigmod(2, cnt));

	return 0;
}

Compilation message (stderr)

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

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