Submission #332084

#	Time	Username	Problem	Language	Result	Execution time	Memory
332084		LucaDantas	Port Facility (JOI17_port_facility)	C++17	22 / 100	6037 ms	6760 KiB

port_facility

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

using pii = pair<int,int>;

#define ss second
#define ff first
#define pb push_back

constexpr int maxn = 1e6+10, mod = 1000000007;

int evt[2*maxn], close[maxn], open[maxn];

struct DSU
{
	int pai[maxn], peso[maxn], cor[maxn], cc, bip;
	void init(int n) {
		cc = n; bip = 1;
		for(int i = 1; i <= n; i++)
			pai[i] = i, peso[i] = cor[i] = 0;
	}
	int find(int x, int& c) {
		while(x != pai[x])
			c ^= cor[x], x = pai[x];
		return x;
	}
	void join(int a, int b) {
		if(a == b) return;
		int c1 = 0, c2 = 0;
		a = find(a, c1), b = find(b, c2);
		if(a == b && c1 == c2) return (void)(bip = 0);
		if(a != b) {
			--cc;
			if(peso[a] < peso[b])
				swap(a, b);
			pai[b] = a;
			peso[a] += peso[b];
			cor[b] = 1^c1^c2;
		}
	}
} dsu;

int power(int b, int e) {
	int ans = 1;
	while(e) {
		if(e&1) ans = (1ll * ans * b % mod);
		b = (1ll * b * b % mod);
		e >>= 1;
	}
	return ans;
}

int main() {
	int n; scanf("%d", &n);
	dsu.init(n);
	for(int i = 1, a, b; i <= n; i++)
		scanf("%d %d", &a, &b), evt[a] = i, evt[b] = -i, close[i] = b, open[i] = a;
	set<pii> st;
	for(int i = 1; i <= 2*n; i++) {
		if(evt[i] > 0) st.insert({open[evt[i]], evt[i]});
		else {
			assert(st.size());
			// if(st.count({open[-evt[i]], -evt[i]}))
				st.erase({open[-evt[i]], -evt[i]});
			if(!st.size()) continue;
			for(auto it = st.upper_bound({open[-evt[i]], -evt[i]}); it != st.end(); ++it) {
				dsu.join(-evt[i], (*it).ss);
				if(!dsu.bip) {puts("0"); return 0;}
			}
		}
	}
	printf("%d\n", dsu.bip?power(2, dsu.cc):0);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
port_facility.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%d %d", &a, &b), evt[a] = i, evt[b] = -i, close[i] = b, open[i] = a;
      |   ~~~~~^~~~~~~~~~~~~~~~~

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