Submission #1126947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126947		Rainmaker2627	Port Facility (JOI17_port_facility)	C++20	0 / 100	1 ms	320 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct dsu {
	int n, cc;
	vector<int> r, s;

	dsu(int n) {
		this->n=n; cc=n;
		r.reserve(n+1);
		for (int i = 1; i <= n; ++i) r[i]=i;
		s.assign(n+1, 1);
	}

	int find(int a) {
		if (a==r[a]) return a;
		return r[a]=find(r[a]);
	}

	bool unite(int a, int b) {
		if (b==-1) return false;
		a=find(a), b=find(b);
		if (a==b) return true;
		if (s[a]<s[b]) swap(a, b);
		r[b]=a; s[a]+=s[b]; cc--;
		return false;
	}
};

int exp(int a, int b, int mod) {
	int x=1;
	while (b) {
		if (b%2) x=(x*a)%mod;
		a=(a*a)%mod; b/=2;
	} return x;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);

	int n;
	cin >> n;
	set<pair<int, int>> s;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		s.insert({a[i], i+1});
		s.insert({b[i], -i-1});
	}

	dsu uf(n);
	vector<int> c, p(n+1);
	for (auto i = s.begin(); i != s.end(); ++i) {
		auto [t, j] = *i;
		if (j>0) {
			p[j]=c.size();
			c.push_back(j);
		} else {
			for (int k = p[-j]+1; k < c.size(); ++k) {
				if (uf.unite(-j, c[k])) { cout << "0\n"; return 0; }
			} c[p[-j]]=-1;
		}
	}

	cout << exp(2, uf.cc, 1e9+7) << '\n';
	return 0;
}

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