Submission #1199141

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)





template<int um> struct UF {
	vector<int> par; UF() { clear(); }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y) { x = operator[](x); y = operator[](y); if (x != y) par[x] = y; }
	void clear() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
};
int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
int mul(int x, int y) { return 1LL * x * y % mod; }
int modpow(int a, long long b) {
	int ret = 1;
	while (b > 0) { if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1; }
	return ret;
}
int modinv(int a) { return modpow(a, mod - 2); }
int fac[201010], ifac[201010];
void initfac() {
	fac[0] = ifac[0] = 1;
	rep(i, 1, 201010) fac[i] = 1LL * i * fac[i - 1] % mod;
	rep(i, 1, 201010) ifac[i] = modinv(fac[i]);
}
//-----------------------------------------------------------------------------------
int N, X, Y, C[201010], W[201010];
UF<201010> uf;
void naive_merge() {
	rep(a, 0, N) rep(b, a + 1, N) {
		if (C[a] == C[b] && W[a] + W[b] <= X) uf(a, b);
		if (C[a] != C[b] && W[a] + W[b] <= Y) uf(a, b);
	}
}
//-----------------------------------------------------------------------------------
void optimized_merge() {
	map<int, vector<pair<int, int>>> color;
	rep(i, 0, N) color[C[i]].push_back({ W[i], i });
	for (auto& g : color) sort(g.second.begin(), g.second.end());

	// same color
	for (auto& g : color) {
		auto v = g.second;
		rep(i, 1, v.size()) if (v[0].first + v[i].first <= X) uf(v[0].second, v[i].second);
	}
	
	// different color
	vector<int> order;
	for (auto& g : color) order.push_back(g.first);
	sort(order.begin(), order.end(), [&](int a, int b) {
		return color[a][0].first < color[b][0].first;
	});
	rep(i, 0, N) { //color[order[0]][0] -> any
		auto p = color[order[0]][0];
		if (p.first + W[i] <= Y && order[0] != C[i]) uf(p.second, i);
	}
	if (2 <= order.size()) rep(i, 0, N) { //color[order[1]][0] -> any
		auto p = color[order[1]][0];
		if (p.first + W[i] <= Y && order[1] != C[i]) uf(p.second, i);
	}
}
//-----------------------------------------------------------------------------------
int count() {
	map<int, vector<int>> group;
	rep(i, 0, N) group[uf[i]].push_back(i);

	int res = 1;
	for (auto g : group) {
		auto v = g.second;
		int com = fac[v.size()];

		map<int, int> cnt;
		for (int i : v) cnt[C[i]]++;
		for (auto p : cnt) com = mul(com, ifac[p.second]);

		res = mul(res, com);
	}

	return res;
}
//-----------------------------------------------------------------------------------
int main() {
	initfac();
	cin >> N >> X >> Y;
	rep(i, 0, N) scanf("%d%d", &C[i], &W[i]);

	//naive_merge();
	optimized_merge();
	cout << count() << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:89:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 0, N) scanf("%d%d", &C[i], &W[i]);
                                          ^

Judge Result