Submission #683632

#	Time	Username	Problem	Language	Result	Execution time	Memory
683632		NK_	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	320 KiB

port_facility

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define mp make_pair

using pi = pair<int, int>;
using E = array<int, 3>;

const int MOD = 1e9+7;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	vector<int> EV(2*N);
	vector<int> A(N), B(N);
	for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i]; --A[i], --B[i];
		EV[A[i]] = i;
		EV[B[i]] = -1;
	}

	vector<vector<pi>> adj(N);

	set<E> S;

	vector<vector<E>> R(2*N);
	for(int t = 0; t < 2*N; t++) {
		// cout << "SET: " << nl;
		// for(auto x : S) {
		// 	cout << x[0] << " " << x[1] << " " << x[2] << nl;
		// }
		// cout << nl;

		int e = EV[t];
		if (e == -1) for(const auto &x : R[t]) S.erase(x);
		else {
			int mx = -1, mn = 1e9;
			vector<E> rem;
			for(const auto &x : S) {
				auto [ti, u, w] = x;

				if (ti > B[e]) break;

				if (w) {
					rem.push_back(x);
					mx = max(mx, ti);
					mn = min(mx, ti);
				}

				// cout << "EDGE: " << u << " " << e << " " << w << nl;
				adj[u].push_back(mp(e, w));
				adj[e].push_back(mp(u, w));
			}	

			if (mx != -1) {
				S.insert({mn, e, 0});
				R[mx].push_back({mn, e, 0});
			}

			S.insert({B[e], e, 1});
			R[B[e]].push_back({B[e], e, 1});

			for(const auto &x : rem) S.erase(x);
		}
	}


	bool bi = 1;

	vector<int> P(N, -1);
	function<void(int)> dfs = [&](int u) {
		for(auto e : adj[u]) {
			int v, w; tie(v, w) = e;
			if (P[v] != -1) bi &= P[v] == (P[u] ^ w);
			else { P[v] = P[u] ^ w; dfs(v); }
		}
	};

	int ans = 1;
	for(int i = 0; i < N; i++) if (P[i] == -1) { P[i] = 0; dfs(i); ans = (2 * ans) % MOD; }

	cout << (!bi ? 0 : ans) << nl;

    return 0;
}

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

5 
1 4 
2 10 
6 9 
7 8 
3 5

3 
1 4 
2 5 
3 6

*/

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