Submission #101747

#	Time	Username	Problem	Language	Result	Execution time	Memory
101747		hugo_pm	Port Facility (JOI17_port_facility)	C++17	100 / 100	2000 ms	124856 KiB

port_facility

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

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }

void cpr(string s) { cpr(s, {}); }

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 2 * ((int)(1e6) + 5); // MODIF POUR OJ !!!
const int MOD = (int)(1e9) + 7;
int nbCas;
pii cas[borne];

// Union-find
int par[borne];
int sz[borne];

void duInit()
{
	form(i, borne) {
		par[i] = i;
		sz[i] = 1;
	}
}

int duFind(int x)
{
	if (par[x] == x) return x;
	return par[x] = duFind(par[x]);
}

void duUnir(int a, int b)
{
	a = duFind(a);
	b = duFind(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b); // a devient gros
	par[b] = a;
	sz[a] += sz[b];
}
// Fin

map<int, int> endToCas;

void solve()
{
	duInit();
	cin >> nbCas;
	form(i, nbCas) cin >> cas[i].fi >> cas[i].se;
	sort(cas, cas+nbCas);

	form(cur, nbCas) {
		int gauche = cas[cur].fi, droite = cas[cur].se;

		auto deb = endToCas.lower_bound(gauche);
		auto mur = endToCas.lower_bound(droite);
		if (mur != endToCas.begin()) {
			auto fin = mur; --fin;
			while (deb != mur) {
				duUnir(cur, deb->se + nbCas);
				duUnir(cur + nbCas, deb->se);

				if (duFind(deb->se) == duFind(fin->se)) break;
				++deb;
			}
		}
		endToCas[droite] = cur;
	}

	int ans = 1;
	form(caisse, nbCas) {
		if (duFind(caisse) == caisse) {
			ans *= 2;
			ans %= MOD;
		}
		// Non-biparti
		if (duFind(caisse) == duFind(caisse + nbCas)) {
			cout << "0\n";
			return;
		}
	}
	cout << ans << "\n";
}

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