Submission #42891

#	Time	Username	Problem	Language	Result	Execution time	Memory
42891		almasalmas	Port Facility (JOI17_port_facility)	C++14	22 / 100	6067 ms	56404 KiB

port_facility

#include <bits/stdc++.h>

#define int long long 

using namespace std;

int mod = 1e9 + 7;
pair <int, int> asd[1000001];
int a[1000001];
int b[1000001];
vector <int> g[1000001];
int kol[1000001];
int cnt[1000001];
int col[1000001];
int u[1000001];
int ans = 1, id;

bool check (int i, int j) {
	if (i == j) return 0;
	int l1 = a[i], r1 = b[i];
	int l2 = a[j], r2 = b[j];
	if (r1 < l2 || r2 < l1) return 0;
	if (l1 > l2 && r1 < r2) return 0;
	if (l2 > l1 && r2 < r1) return 0;
	return 1;
}

void dfs (int v, int lvl) {
	u[v] = lvl;     
	col[v] = id;
	cnt[id] ++;
	for (auto to : g[v]) {
		if (u[to] == u[v]) {
			cout << 0;
			exit (0);
		}
		if (!u[to]) {
			dfs (to, 3 - lvl);
		}
	}
}

 main () {
 	int n;
 	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> asd[i].first >> asd[i].second;
	}
	sort (asd + 1, asd + n + 1);
	for (int i = 1;i <= n;i ++) {
		a[i] = asd[i].first;
		b[i] = asd[i].second;
	}
//	cout << endl;
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= n;j ++) {
			if (check (i, j)) {
				g[i].push_back (j);
//				cout << i << ' ' << j << endl;
			}
		}
	}
	for (int i = 1;i <= n;i ++) {
		if (!u[i]) {
			id ++;
			dfs (i, 1);
			ans = (ans + ans) % mod;
		}
	}       
	for (int i = 1;i <= n;i ++) {
		for (int j = i + 1;j <= n;j ++) {
			if (check (i, j)) {
				kol[col[i]] ++;
			}
		}
	}
/*	for (int i = 1;i <= id;i ++) {
	//	cout << kol[i] << ' ' << cnt[i] << endl;
		if (kol[i] % 2 == 1 && kol[i] != cnt[i] - 1) {
			cout << 0;
			return 0;
		}
	}             */
	cout << ans;
	return 0;
}

Compilation message (stderr)

port_facility.cpp:43:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main () {
        ^

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