https://beta.atcoder.jp/contests/agc012/tasks/agc012_d
最初の提出で3ケースだけWAだったのでオーバーフローとかどうでもいいミスでしょと思いましたが違いました…
同じ色内だったら1番小さいやつから辺を張ればいいです。
でも違う色だったら色の中で一番小さいやつのうち一番小さいの+二番目に小さいのから辺を張る必要があります。
二番目も張らないといけないの、当たり前だけど気づかなかった…
さらに実装も一部ミスがあり、どっちもミスった結果大体のケースで正答を出すようなプログラムを書いてしまいました。
int N; ll X, Y; vector<pl> group[MAX_N]; pl mel[MAX_N]; ll C[MAX_N], W[MAX_N]; vector<int> con[MAX_N]; int cnt[MAX_N]; void solve() { cin >> N >> X >> Y; C_init(N); rep(i, 0, N) { cin >> C[i] >> W[i]; C[i]--; group[C[i]].pb(pl(i, W[i])); } UF uf(N); fill(mel, mel + N, pl(linf, linf)); rep(i, 0, N) { vector<pl>& g = group[i]; int at = -1; ll w = linf; rep(i, 0, sz(g)) { pl p = g[i]; if(w > p.sec) { w = p.sec; at = p.fst; } } mel[i] = pl(w, at); rep(i, 0, sz(g)) { pl p = g[i]; if(p.sec + w <= X) uf.unite(at, p.fst); } } sort(mel, mel + N); rep(i, 0, min(2, N)) { int at = mel[i].sec; ll w = mel[i].fst; rep(j, 0, N) { if(C[at] != C[j] && w + W[j] <= Y) uf.unite(j, at); } } rep(i, 0, N) con[uf.find(i)].pb(i); ll ans = 1; int at = uf.find(mel[0].sec); vi& vec = con[at]; rep(i, 0, sz(vec)) cnt[C[vec[i]]]++; ans = fac[sz(vec)]; rep(i, 0, N) MUL(ans, fiv[cnt[i]]); cout << ans << "\n"; }