Submission #1299385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299385		kian2009	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	332 KiB

port_facility

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e6 + 10, mod = 998244353;

int n, sz[MAXN], w[MAXN][2];
pii p[MAXN], par[MAXN];
vector<int> del;
set<pii> s;
bool use[MAXN], ans = true;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i].f >> p[i].s;
	sort(p, p + n);
}

pii find(int u) {
	if (par[u].f == u)
		return par[u];
	pii res = find(par[u].f);
	par[u] = {res.f, res.s ^ par[u].s};
	return res;	
}

bool merge(int u, int v) {
	pii u1 = find(u);
	pii v1 = find(v);
	if (u1.f == v1.f) {
		if (u1 == v1)
			return false;
		return true;
	}
	if (sz[u1.f] > sz[v1.f])
		swap(u1, v1);
	sz[v1.f] += sz[u1.f];
	par[u1.f] = {v1.f, ((u1.s ^ v1.s) ^ 1)};
	return true;
}

void findComp() {
	for (int i = 0; i < n; i++) {
		w[i][0] = w[i][1] = -1;
		sz[i] = 1;
		par[i] = {i, 0};
	}
	for (int i = 0; i < n; i++) {
		if (!s.empty()) {
			auto h = s.lower_bound({p[i].f, -1});
			for (; h != s.end(); h++) {
				int u = (*h).s;
				if (p[u].s > p[i].s)
					break;
				if (!merge(u, i)) {
					ans = false;
					return;	
				}
			}
		}	
		s.insert({p[i].s, i});
		/*del.clear();
		if (!s.empty()) {
			auto h = s.lower_bound({p[i].s, -1});
			for (; h != s.end(); h++) {
				int u = (*h).s;
				del.push_back(u);
				pii u1 = find(u);
				w[u1.f][u1.s] = -1;
				if (w[u1.f][!u1.s] != -1)
					del.push_back(w[u1.f][!u1.s]);
				w[u1.f][!u1.s] = -1;
				cerr << u << " , " << i << endl;
				if (!merge(u, i)) {
					ans = false;
					return;
				}
			}
		}
		del.push_back(i);
		int ma[2] = {-1, -1};
		for (auto u : del) {
			pii u1 = find(u);
			if (ma[u1.s] == -1 || p[u].s > p[ma[u1.s]].s)
				ma[u1.s] = u;
			s.erase({p[u].s, u});	
		}
		del.clear();
		int c = find(i).f;
		if (ma[0] != -1) {
			w[c][0] = ma[0];
			s.insert({p[ma[0]].s, ma[0]});
		}
		if (ma[1] != -1) {
			w[c][1] = ma[1];
			s.insert({p[ma[1]].s, ma[1]});	
		}*/
	}
}

int findAns() {
	for (int i = 0; i < n; i++)
		use[find(i).f] = true;
	int res = 1;
	for (int i = 0; i < n; i++)
		if (use[i])
			res = (res * 2) % mod;
	return res;	
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	findComp();
	if (!ans)
		cout << 0 << endl;
	else
		cout << findAns() << endl;
	return 0;
}

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