Submission #392055

#	Time	Username	Problem	Language	Result	Execution time	Memory
392055		peijar	Port Facility (JOI17_port_facility)	C++17	100 / 100	1100 ms	165104 KiB

port_facility

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

struct UnionFind
{
	vector<int> id;

	UnionFind(int N) : id(N, -1) {}

	int find(int i)
	{
		return id[i] < 0 ? i : id[i] = find(id[i]);
	}

	void merge(int a, int b)
	{
		a = find(a), b = find(b);
		if (a == b) return;
		id[a] += id[b];
		id[b] = a;
	}
};

const int MOD = 1e9 + 7;
const int MAXN = 1e6;
vector<int> adj[MAXN];
int event[2 * MAXN];
priority_queue<int, vector<int>, greater<int>> pqCC[MAXN];
bool vu[MAXN],seen[MAXN];
int side[MAXN];
UnionFind uf(MAXN);

auto comp = [](int i, int j)
{
	return pqCC[i].top() > pqCC[j].top();
};

priority_queue<int, vector<int>, decltype(comp)> ccEnVies(comp);

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbConteneurs;
	cin >> nbConteneurs;

	vector<pair<int, int>> conteneurs(nbConteneurs);
	for (auto &[deb, fin] : conteneurs)
	{
		cin >> deb >> fin;
		--deb, --fin;
	}
	sort(conteneurs.begin(), conteneurs.end());
	for (int i(0); i < nbConteneurs; ++i)
		event[conteneurs[i].first] = event[conteneurs[i].second] = i;


	vector<int> block(2 * nbConteneurs, -1);
	
	for (int iCont(0); iCont < nbConteneurs; ++iCont)
	{
		auto [deb, fin] = conteneurs[iCont];
		int curCC = iCont;
		pqCC[curCC].push(fin);

		while (!ccEnVies.empty())
		{
			int iCC = ccEnVies.top(); ccEnVies.pop();
		
			// On vire les inutiles : 
			if (pqCC[iCC].top() < deb)
			{
				while (!pqCC[iCC].empty() and pqCC[iCC].top() < deb)
					pqCC[iCC].pop();
				if (!pqCC[iCC].empty())
					ccEnVies.push(iCC);
				continue;
			}

			// On a plus d'aretes :
			if (pqCC[iCC].top() > fin)
			{
				ccEnVies.push(iCC);
				break;
			}

			block[iCont] = event[pqCC[iCC].top()];
			adj[iCont].push_back(block[iCont]);
			adj[block[iCont]].push_back(iCont);
			// On a une arete : 
			// On fusionne les cc
			if (uf.id[curCC] > uf.id[iCC])
				swap(curCC, iCC);
			uf.merge(curCC, iCC);
			assert(uf.find(curCC) == curCC);
			while (!pqCC[iCC].empty())
			{
				pqCC[curCC].push(pqCC[iCC].top());
				pqCC[iCC].pop();
			}
		}
		ccEnVies.push(curCC);
	}
	
	queue<int> q;
	for (int i = 0; i < nbConteneurs; ++i) 
		if (uf.id[i] < 0)
			q.push(i);

	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		seen[cur] = true;
		for (auto nxt : adj[cur])
			if (!seen[nxt])
			{
				side[nxt] = !side[cur];
				q.push(nxt);
			}
	}

	stack<int> stk[2];
	for (int t(0); t < 2 * nbConteneurs; ++t)
	{
		int id = event[t];
		if (vu[id])
		{
			if (stk[side[id]].top() != id)
			{
				cout << 0 << endl;
				return 0;
			}
			stk[side[id]].pop();
		}
		else
		{
			vu[id] = true;
			stk[side[id]].push(id);
		}
	}
	int nbCC(0);
	for (int i(0); i < nbConteneurs; ++i)
		nbCC += uf.id[i] < 0;
	int ret = 1;
	for (int i(0); i < nbCC; ++i)
		ret = (ret * 2) % MOD;
	cout << ret << endl;

}

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