Submission #366687

#	Time	Username	Problem	Language	Result	Execution time	Memory
366687		Rainbowbunny	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	364 KiB

port_facility

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>

const int mod = 1e9 + 7;

int n;
int ans = 1;
int dsu[1000005], H[1000005], Rank[1000005];
int A[1000005], B[1000005];
int Event[2000005];

int Root(int node)
{
	return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}

void Union(int u, int v)
{
	u = Root(u);
	v = Root(v);
	if(u != v)
	{
		if(Rank[u] > Rank[v])
		{
			std::swap(u, v);
		}
		dsu[v] = u;
		if(Rank[u] == Rank[v])
		{
			Rank[u]++;
		} 
	}
	else
	{
		std::cout << 0;
		exit(0);
	}
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n;
	for(int i = 1; i <= n; i++)
	{
		Rank[i] = 0;
		dsu[i] = i;
		std::cin >> A[i] >> B[i];
		Event[A[i]] = i;
		Event[B[i]] = -i;
	}
	std::set <std::pair <int, int> > S;
	std::set <int> T;
	for(int i = 1; i <= 2 * n; i++)
	{
		if(Event[i] > 0)
		{
			for(auto x : S)
			{
				if(x.first > B[Event[i]])
				{
					break;
				}
				Union(x.second, Event[i]);
			}
			S.insert(std::make_pair(B[Event[i]], Event[i]));
		}
		else
		{
			S.erase(std::make_pair(B[-Event[i]], -Event[i]));
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(Root(i) == i)
		{
			ans = ans * 2;
			if(ans >= mod)
			{
				ans -= mod;
			}
		}
	}
	std::cout << ans;
}

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