제출 #771402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
771402		NK_	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	324 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 f first
#define s second
#define mp make_pair

using ll = long long;
using pi = pair<int, int>;
template<class T> using V = vector<T>;
using vi = V<int>;

struct DSU {
	vi e; V<set<pi>> S; void init(int N) { e = vi(N, -1); S = V<set<pi>>(N); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	void ins(int x, pi v) { x = get(x); S[x].insert(v); }
	void erase(int x, pi v) { x = get(x); assert(S[x].find(v) != S[x].end()); S[x].erase(v); }
	int siz(int x) { return size(S[get(x)]); }
	pi top(int x) { return *begin(S[get(x)]); }
	pi top2(int x) { return *next(begin(S[get(x)])); }


	bool unite(int x, int y) {
		x = get(x), y = get(y); if (x == y) return 0;
		// assert(x != y);
		if (e[x] > e[y]) swap(x, y);
		for(auto& v : S[y]) S[x].insert(v);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	V<pi> E(2*N);

	vi A(N), B(N); for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i]; --A[i], --B[i];
		E[A[i]] = mp(i, +1);
		E[B[i]] = mp(i, -1);
	}

	V<vi> adj(N);

	auto ae = [&](int u, int v) {
		// cout << u << " " << v << endl;
		adj[u].push_back(v);
		adj[v].push_back(u);
	};

	DSU D; D.init(N); 
	set<pi> R;
	for(int t = 0; t < 2 * N; t++) {
		int i = E[t].f;
		// cout << t << " -> " << i << endl;
		if (E[t].s == +1) {
			vi conn;
			for(auto r : R) {
				if (r.f > B[i]) break;
				conn.push_back(r.s);
				// cout << i << " - " << r.s << endl;
			}

			for(auto x : conn) {
				D.unite(x, i); ae(i, x);

				if (D.siz(x) > 1) {
					pi p = D.top2(x);
					// cout << i << " " << p.s << " " << p.f << endl;
					if (B[i] > p.f) ae(i, p.s);
				}
			}

			D.ins(i, mp(B[i], i));
			if (size(conn) == 0) R.insert(D.top(i));
		}

		if (E[t].s == -1) {
			R.erase(D.top(i));
			D.erase(i, mp(B[i], i));
			if (D.siz(i) > 0) R.insert(D.top(i));
		}
	}
	// cout << ans << nl;


	vi C(N, -1); bool bi = 1;
	function<void(int)> dfs = [&](int u) {
		// cout << u << endl;
		for(auto& v : adj[u]) {
			if (C[v] == -1) C[v] = C[u] ^ 1, dfs(v);
			else {
				if (C[v] == C[u]) bi = 0;
			}
		}
	};

	int ans = 0;
	for(int i = 0; i < N; i++) if (C[i] == -1) {
		ans++; C[i] = 0; dfs(i);
		// cout << endl;
	}

	if (!bi) {
		cout << 0 << nl;
		return 0;
	}

	const int MOD = 1e9 + 7;
	ll ANS = 1, x = 2;

	for(; ans; ans /= 2, x = (x * x) % MOD) if (ans & 1) ANS = (ANS * x) % MOD;

	cout << ANS << nl;







    return 0;
}

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