Submission #392034

#	Time	Username	Problem	Language	Result	Execution time	Memory
392034		peijar	Port Facility (JOI17_port_facility)	C++17	0 / 100	0 ms	204 KiB

port_facility

#include <bits/stdc++.h>
#define int long long
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;
		if (id[a] > id[b]) {assert(false); swap(a, b);}
		id[a] += id[b];
		id[b] = a;
	}
};

const int MOD = 1e9 + 7;

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());
	vector<int> event(2*nbConteneurs);
	for (int i(0); i < nbConteneurs; ++i)
		event[conteneurs[i].first] = event[conteneurs[i].second] = i;

	vector<priority_queue<int, vector<int>, greater<int>>> pqCC(nbConteneurs);
	
	auto comp = [&](int i, int j) 
	{
		return pqCC[i].top() > pqCC[j].top();
	};
	vector<bool> vu(nbConteneurs);

	UnionFind uf(nbConteneurs);

	priority_queue<int, vector<int>, decltype(comp)> ccEnVies(comp);
	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()];
			// 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);
	}
	
	vector<int> side(nbConteneurs);
	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();
			continue;
		}
		vu[id] = true;
		if (block[id] == -1)
			side[id] = 0;
		else
			side[id] = !side[block[id]];
		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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22