Submission #45589

#	Time	Username	Problem	Language	Result	Execution time	Memory
45589		maksim_gaponov	Port Facility (JOI17_port_facility)	C++14	22 / 100	6072 ms	17620 KiB

port_facility

#define _CRT_SECURE_NO_WARNINGS
#ifdef _DEBUG
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;

void openFiles() {
#ifdef _DEBUG
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

vector<vector<int>> g;
vector<bool> used;
vector<int> color;
ll ans = 1;

void dfs(int i) {
	used[i] = true;
	if (color[i] == 0)
		color[i] = 1;
	for (auto j : g[i]) {
		if (color[j] == color[i]) {
			cout << "0";
			exit(0);
		}
		if (!used[j]) {
			color[j] = -color[i];
			dfs(j);
		}
	}
}

int main() {
	openFiles();
	IOoptimize();
	int n;
	cin >> n;
	g.resize(n);
	vector<pair<int, int>> segments;
	for (int i = 0; i < n; i++) {
		int time1, time2;
		cin >> time1 >> time2;
		segments.push_back({time1, time2});
	}
	sort(segments.begin(), segments.end());
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (segments[j].first < segments[i].second && segments[i].second < segments[j].second) {
				g[i].push_back(j);
				g[j].push_back(i);
				//cout << i + 1 << " -> " << j + 1 << "\n";
			}
		}
	}
	color.resize(n, 0);
	used.resize(n, false);
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			dfs(i);
			ans *= 2;
			ans %= mod;
		}
	}
	cout << ans;
	return 0;
}

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