제출 #1226404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226404		PenguinsAreCute	Port Facility (JOI17_port_facility)	C++17	0 / 100	0 ms	320 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	int a[n], b[n], pref[2*n+1], cur[2*n];
	bool vis[n];
	vector<int> adj[n];
	memset(pref,0,sizeof(pref));
	for(int i=0;i<n;i++) {
		cin >> a[i] >> b[i];
		pref[--a[i]]++;
		pref[b[i]]--;
	}
	partial_sum(pref,pref+2*n,pref);
	for(int i=0;i<2*n;i++)
		if(pref[i] >= 3) {
			cout << 0;
			return 0;
		}
	memset(cur,-1,sizeof(cur));
	for(int i=0;i<n;i++)
		for(int j=a[i];j<b[i];j++)
			if(cur[j] == -1)
				cur[j] = i;
			else {
				adj[cur[j]].push_back(i);
				adj[i].push_back(cur[j]);
			}
	memset(vis,0,sizeof(vis));
	int ans = 1;
	for(int i=0;i<n;i++)
		if(!vis[i]) {
			queue<int> q;
			q.push(i);
			vis[i] = 1;
			ans = (2 * ans) % (1'000'000'007);
			while(q.size()) {
				int x = q.front();
				q.pop();
				for(auto y: adj[x])
					if(!vis[y]) {
						vis[y] = 1;
						q.push(y);
					}
			}
		}
	cout << ans;
}

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