Submission #42884

#	Time	Username	Problem	Language	Result	Execution time	Memory
42884		almasalmas	Port Facility (JOI17_port_facility)	C++14	22 / 100	6019 ms	35664 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[100001];
int u[100001];
int ans = 1;

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;
	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]) {
			dfs (i, 1);
			ans = (ans + ans) % mod;
		}
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

port_facility.cpp:38: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