Submission #55742

#	Time	Username	Problem	Language	Result	Execution time	Memory
55742		ksun48	Port Facility (JOI17_port_facility)	C++14	0 / 100	33 ms	26584 KiB

port_facility

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

const LL MOD = 1000000007;

mt19937 mt(48);

int ans = 1;
vector<int> edges[1100000];
int color[1100000];
void dfs(int a, int c){
	if(color[a] == -c){
		ans = 0;
	}
	if(ans == 0) return;
	if(color[a] == c) return;
	for(int b : edges[a]){
		dfs(b, -c);
	}
}
int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	vector<LL> ship(2*n);
	vector<pair<int,int> > nums;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		nums.push_back({a,b});
		ship[a] = ship[b] = mt();
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			int a = nums[i].first >= nums[j].first && nums[i].first <= nums[j].second;
			int b = nums[i].first >= nums[j].first && nums[i].first <= nums[j].second;
			if(a != b){
				edges[i].push_back(j);
			}
		}
	}
	for(int i = 0; i < n; i++){
		color[i] = 0;
	}
	for(int i = 0; i < n; i++){
		if(color[i] == 0){
			dfs(i, 1);
		}
	}

	LL cur = 0;
	set<LL> seen;
	seen.insert(cur);
	for(int i = 0; i < 2*n; i++){
		cur ^= ship[i];
		if(seen.find(cur) != seen.end()){
			ans = (ans * 2) % MOD;
		}
		seen.insert(cur);
	}
	cout << ans << '\n';
}

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