コンテンツにスキップ

ABC478 E - lt and le

サイト
AtCoder
コンテスト
ABC478
問題
E - lt and le
難易度
1376

11 以上 NN 以下の整数からなる長さ NN の列 AA で、QQ 個の条件「Au≤AvA_u \le A_v」または「Au<AvA_u < A_v」をすべて満たすものがあるかを判定し、あれば 1 つ出力する問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

条件 Au≤AvA_u \le A_v、Au<AvA_u < A_v のどちらも、頂点 uu から vv への辺だと思ってグラフを作り、強連結成分(SCC)分解します。

  • 同じ SCC の中の頂点は、辺をたどって一周できるので、Au≤⋯≤AuA_u \le \cdots \le A_u となり、すべて同じ値でなければなりません。したがって、<< の辺の両端が同じ SCC にあれば No です。
  • そうでなければ、SCC をトポロジカル順に並べたときの番号(11 始まり)をそのまま AA にすれば条件をすべて満たします。異なる SCC 間の辺は必ず番号が増える向きなので << も ≤\le も満たし、同じ SCC 内の辺はすべて ≤\le なので等しい値で満たします。番号は NN 以下です。

ACL の scc_graph::scc() は成分をトポロジカル順に返すので、その添字をそのまま使えます。計算量は O(N+Q)O(N + Q) です。

本番では次の方針で提出し、AC しました。

  1. ≤\le の辺だけで SCC 分解し、同じ成分を「等しい値になるグループ」として DSU でまとめる
  2. すべての辺で SCC 分解し、異なるグループが同じ SCC に入ったら No
  3. そうでなければ SCC の番号を出力する

ところが、同じグループ(等しくなることが決まった頂点どうし)の間に << の辺がある場合を見落としていました。<< の辺で弾いていたのは u=vu = v のときだけです。たとえば

2 3
0 1 2
0 2 1
1 1 2

は A1=A2A_1 = A_2 が必要なのに A1<A2A_1 < A_2 も要求されているので答えは No ですが、本番のコードは Yes と 1 1 を出力してしまいます。テストケースにこの形がなかったため通ってしまったようです。

上の解法のように、<< の辺の両端が同じ SCC にあるかを最後に確かめれば、この場合も正しく No になります(修正版で AC を確認しました)。そもそも DSU も 2 回目の SCC も要らず、SCC 1 回で十分でした。

C++(修正版・AC)
#include "atcoder/scc"
#include "sh-library/base/all"
void solve() {
LL(N, Q);
VAL(TUV, Q, 3);
atcoder::scc_graph g(N);
for (auto &[t, u, v] : TUV) {
u--, v--;
g.add_edge(u, v);
}
auto scc = g.scc();
vl ans(N);
rep(i, scc.size()) {
for (ll x : scc[i])
ans[x] = i + 1;
}
for (auto [t, u, v] : TUV) {
if (t == 1 and ans[u] == ans[v]) {
No;
}
}
print("Yes");
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

使用ライブラリ:cpp_include@6c2f83f

C++(本番の提出・嘘解法)
#include "atcoder/dsu"
#include "atcoder/scc"
#include "sh-library/base/all"
void solve() {
LL(N, Q);
VAL(TUV, Q, 3);
atcoder::dsu h(N);
{
atcoder::scc_graph g0(N);
for (auto &[t, u, v] : TUV) {
u--, v--;
if (t == 0) {
g0.add_edge(u, v);
} else {
if (u == v) {
print("No");
return;
}
}
}
auto tmp = g0.scc();
for (auto &x : tmp) {
rep(i, 1, x.size()) {
h.merge(x[0], x[i]);
}
}
}
{
atcoder::scc_graph g(N);
for (auto &[t, u, v] : TUV) {
if (t == 0 && h.same(u, v)) {
g.add_edge(v, u);
}
g.add_edge(u, v);
}
auto tmp = g.scc();
for (auto &x : tmp) {
rep(i, 1, x.size()) {
if (h.same(x[0], x[i]))
continue;
print("No");
return;
}
}
vl ans(N);
rep(i, tmp.size()) {
for (ll a : tmp[i]) {
ans[a] = i + 1;
}
}
print("Yes");
print(ans);
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

使用ライブラリ:cpp_include@6c2f83f