Submission #21312

#	Time	Username	Problem	Language	Result	Execution time	Memory
21312		kingpig9	Port Facility (JOI17_port_facility)	C++11	22 / 100	3500 ms	33272 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2e6 + 10;

struct union_find {
	int par[MAXN];

	union_find() {
		iota(par, par + MAXN, 0);
	}

	int find (int x) {
		return x == par[x] ? x : par[x] = find(par[x]);
	}

	void merge (int x, int y) {
		par[find(x)] = find(y);
	}
} uf, uf2;

int N;
int A[MAXN], B[MAXN];

int main() {
	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &A[i], &B[i]);
		for (int j = 1; j < i; j++) {
			if (!((A[i] < A[j] && B[j] < B[i]) || (A[j] < A[i] && B[i] < B[j]) || B[j] < A[i] || B[i] < A[j])) {
				uf.merge(2 * i, 2 * j + 1);
				uf.merge(2 * i + 1, 2 * j);
				uf2.merge(i, j);
			}
		}
	}

	for (int i = 2; i <= 2 * N; i += 2) {
		if (uf.find(i) == uf.find(i + 1)) {
			puts("0");
			return 0;
		}
	}

	int ans = 1;
	for (int i = 1; i <= N; i++) {
		if (uf2.find(i) == i) {
			ans = (ans * 2) % 1000000007;
		}
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:26:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
port_facility.cpp:29:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &A[i], &B[i]);
                               ^

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