Submission #211499

#	Time	Username	Problem	Language	Result	Execution time	Memory
211499		mode149256	Port Facility (JOI17_port_facility)	C++14	100 / 100	2872 ms	191612 KiB

port_facility

/*input
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12

3
1 4
2 5
3 6

5
1 4
2 10
6 9
7 8
3 5

*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

vi rankas;
vi p;
vi edges[(int)1e6];
vpi poros;
vi kas;
int N;

int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j) {
	edges[kas[i]].emplace_back(kas[j]);
	edges[kas[j]].emplace_back(kas[i]);

	if (isSameSet(i, j)) {
		printf("0\n");
		exit(0);
	}

	int x = findSet(i), y = findSet(j);
	if (rankas[x] > rankas[y]) p[y] = x;
	else {
		p[x] = y;
		if (rankas[x] == rankas[y]) rankas[y]++;
	}
}

vb been(1e6, false);
vi keliai[2];
vi kitas;
void dfs(int x, int h) {
	been[x] = true;
	keliai[h].emplace_back(poros[x].x);
	keliai[h].emplace_back(poros[x].y);

	h = 1 - h;
	for (auto u : edges[x])
		if (!been[u])
			dfs(u, h);
}

bool blogas() {
	for (int n = 0; n < N; ++n)
	{
		if (been[n]) continue;
		keliai[0].clear();
		keliai[1].clear();

		dfs(n, 0);
		sort(keliai[0].begin(), keliai[0].end());
		sort(keliai[1].begin(), keliai[1].end());

		// printf("n = %d\n", n);
		// print(keliai[0], "keliai[0]: ");
		// print(keliai[1], "keliai[1]: ");

		stack<int> stak;
		for (auto u : keliai[0]) {
			if (u < kitas[u]) stak.push(kitas[u]);
			else {
				if (stak.top() != u) return true;
				stak.pop();
			}
		}

		for (auto u : keliai[1]) {
			if (u < kitas[u]) stak.push(kitas[u]);
			else {
				if (stak.top() != u) return true;
				stak.pop();
			}
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;

	p = vi(2 * N + 1); for (int i = 0; i <= 2 * N; i++) p[i] = i;
	rankas = vi(2 * N + 1, 0);
	kas = vi(2 * N + 1);
	kitas = vi(2 * N + 1);
	for (int i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;
		kitas[a] = b;
		kitas[b] = a;
		unionSet(a, b);
		kas[a] = kas[b] = i;
		poros.emplace_back(a, b);
	}

	ll ats = 1;

	// sort(poros.begin(), poros.end());

	set<int> visos;
	set<int> reikalingos;

	for (int i = 1; i <= 2 * N; i++) {
		if (i < kitas[i]) {
			int a = i;
			int b = kitas[i];

			if (reikalingos.empty()) {
				visos.insert(b);
				reikalingos.insert(b);
				continue;
			}

			auto it = reikalingos.begin();
			int prad = *it;

			if (b < prad) reikalingos.insert(b);
			else {
				while (it != reikalingos.end() and * it < b) {
					// printf("jungiu i = %d, it = %d\n", i, *it);
					unionSet(i, *it);

					auto prev = it;
					it = next(it);

					reikalingos.erase(prev);
				}
				reikalingos.insert(prad);
			}

			visos.insert(b);
		} else {
			visos.erase(i);
			reikalingos.erase(i);
			if (visos.size())
				reikalingos.insert(*visos.begin());
		}
	}

	if (blogas()) {
		printf("0\n");
		return 0;
	}

	vb buvo(2 * N + 1, false);
	for (int i = 1; i <= 2 * N; ++i)
	{
		if (!buvo[findSet(i)]) ats = (ats * 2) % MOD;
		buvo[findSet(i)] = true;
	}
	printf("%lld\n", ats);
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:180:8: warning: unused variable 'a' [-Wunused-variable]
    int a = i;
        ^

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