コンテンツにスキップ

グラフ

タグ「グラフ」の記事 9 件

SamCoding Round 9 (Div. 4) F - Two-Coloured Graph

nn 頂点 mm 辺の無向グラフが与えられます。多重辺はありますが、自己ループはありません。連結とは限りません。各頂点を白か黒に塗り、どの辺も両端の色が異なるようにするとき、黒い頂点の数の最小値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、0≤m≤2×1050 \le m \le 2 \times 10^5)。そのような塗り方がなければ −1-1 を出力します。

どの辺も両端の色が異なるように 2 色で塗れるのは、グラフが二部グラフのときです。二部グラフでなければ答えは −1-1 です。

二部グラフのとき、連結成分ごとに考えます。連結成分の中では、1 つの頂点の色を決めると、辺をたどって隣の頂点の色が次々に決まるので、成分全体の色も決まります。そのため、各連結成分の塗り方は、BFS や DFS で 2 色に塗り分けたものと、その白黒を入れ替えたものの 2 通りしかありません。

連結成分ごとに独立に選べるので、それぞれの成分で 2 色のうち少ないほうを黒にし、その個数を足し合わせたものが答えです。辺のない頂点だけの成分は白にすればよいので 00 個です。全体で O(n+m)O(n + m) です。

例えば入力例 1 では、成分 {1,2,3,4}\{1, 2, 3, 4\} は {1}\{1\} と {2,3,4}\{2, 3, 4\}、成分 {5,6}\{5, 6\} は {5}\{5\} と {6}\{6\} に分かれ、成分 {7}\{7\} は 00 個なので、答えは 1+1+0=21 + 1 + 0 = 2 です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/graph_util.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
Graph<> g(N);
g.read(M);
auto tmp = bipartite_coloring(g);
if (tmp.empty()) {
print(-1);
return;
}
auto cc = connected_components(g);
ll ans = 0;
for (const auto &c : cc) {
al<2> cnt = {0, 0};
for (ll u : c) {
cnt[tmp[u]]++;
}
ans += min(cnt);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

bipartite_coloring は各頂点の色(00 か 11)を返し、二部グラフでなければ空の配列を返します。connected_components は連結成分ごとの頂点の一覧です。成分ごとに色 00 と色 11 の個数を数え、少ないほうを足しています。

使用ライブラリ:cpp_include@4b58304

ABC481 F - Evil Shortest Path

NN 頂点 MM 辺の有向グラフがあり、各辺には 11 以上 99 以下の数字が書かれています。通った辺の数字を順につなげた整数をその移動のスコアとします。v=2,3,…,Nv = 2, 3, \ldots, N のそれぞれについて、頂点 11 から頂点 vv へ移動するときのスコアの最小値を 998244353998244353 で割ったあまりを求める問題です。

同じ頂点や辺を何度通ってもよく、頂点 11 から全頂点に到達できることが保証されます(2≤N≤2×1052 \le N \le 2 \times 10^5、N−1≤M≤2×105N - 1 \le M \le 2 \times 10^5)。

辺の数字はどれも 11 以上なので、スコアの桁数は通った辺の本数に等しく、桁数が少ないほどスコアは小さくなります。よって、スコアが最小になる移動は、頂点 11 からの最短路(辺の本数が最小の移動)のどれかです。桁数が同じ整数どうしの大小は、数字の列の辞書順と一致するので、最短路のうち数字の列が辞書順で最小のものを求めればよいです。

頂点 11 からの最短距離 dd を BFS で求めます。最短路で使える辺は、dv=du+1d_v = d_u + 1 を満たす辺 u→vu \to v だけです。頂点 vv への辞書順最小の列を svs_v とすると、

sv=min⁡u→v, dv=du+1(su の後ろに辺の数字をつなげた列)s_v = \min_{u \to v,\ d_v = d_u + 1} (s_u \text{ の後ろに辺の数字をつなげた列})

です。長さの同じ列どうしでは、sus_u より大きい列の後ろに数字をつなげても、sus_u の後ろにつなげた列より小さくはならないからです。dd の小さい順に頂点を見ていけば、sus_u を使うときには sus_u が確定しています。

列 svs_v の長さは最大で N−1N - 1 になるので、すべての列をそのまま持つと間に合いません。そこで、列を Trie のノードで表します。sus_u のノードから辺の数字で 1 文字進んだノードが「sus_u の後ろに数字をつなげた列」です。1 本の辺でノードは高々 1 個しか増えないので、ノードは M+1M + 1 個以下です。

2 つのノードの列の辞書順の比較は、2 つのノードの最小共通祖先(LCA)のすぐ下の文字を比べればできます。ノードごとに祖先への飛び先を持っておけば、LCA は O(log⁡N)O(\log N) で求まります。

答えのあまりは、svs_v を更新するたびに (su のあまり)×10+(数字)(s_u \text{ のあまり}) \times 10 + (\text{数字}) として一緒に更新します。計算量は O((N+M)log⁡N)O((N + M) \log N) です。

なお、Trie を使わなくても、同じ距離の頂点どうしの svs_v の順位を距離ごとに求めておき、「sus_u の順位、辺の数字」の組をソートして次の距離の順位を決める方法でも解けます。

別解:スコアを距離にしてダイクストラ法

Section titled “別解:スコアを距離にしてダイクストラ法”

スコアを「数字の列の長さで比べ、長さが同じなら辞書順で比べる」値と考えると、この問題はスコアを距離とする最短路問題です。この距離には次の 2 つの性質があります。

  • 辺をたどると、列が 1 文字長くなるので、距離は必ず大きくなる。
  • 列 aa が列 bb より小さければ、同じ数字をつなげた後も、aa のほうが bb 以下になる。

この 2 つが成り立つので、ダイクストラ法がそのまま使えます。距離は上と同じく Trie のノードで持ち、比較 1 回が O(log⁡N)O(\log N) なので、全体の計算量は O(Mlog⁡Mlog⁡N)O(M \log M \log N) です。BFS の層ごとに処理する工夫を、ダイクストラ法に任せる形になります。

C++(BFS)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
#include "shogo-library/utility/vector_func.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, false).dist;
Trie<9, 1> trie;
vl node(N, -1);
vec<mint> ans(N);
node[0] = 0;
for (ll u : sorted_idx(d)) {
for (auto &e : g[u]) {
if (d[e.dst] != d[u] + 1)
continue;
ll v = trie.extend(node[u], e.cost);
if (node[e.dst] == -1 || trie.less(v, node[e.dst])) {
node[e.dst] = v;
ans[e.dst] = ans[u] * 10 + e.cost;
}
}
}
rep(v, 1, N) print(ans[v]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

g.read(M, -1, true, true) は、辺の数字を重みとして、有向辺を MM 本読みます。shortest_path(g, 0, false) の第 3 引数 false は重みを無視することを表し、BFS で辺の本数の最短距離を求めます。

Trie<9, 1> は、文字 11 から 99 を使う Trie です。根(ノード 00)が空の列で、頂点 11 の列に対応します。node[v] は svs_v のノード、ans[v] はそのあまりです。

sorted_idx(d) は d の小さい順に並べた頂点の番号の列です。trie.extend(node[u], e.cost) で sus_u の後ろに辺の数字をつなげた列のノードを(なければ作って)求め、trie.less(v, node[e.dst]) で、いまの svs_v より辞書順で小さいかを O(log⁡N)O(\log N) で比べています。

使用ライブラリ:cpp_include@4b58304

C++(ダイクストラ法)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
using mint = modint998244353;
Trie<9, 1> trie;
struct Score {
ll node = 0;
ll digit = 0;
mint val = 0;
Score() = default;
Score(ll digit) : digit(digit) {}
static Score inf() {
Score res;
res.node = -1;
return res;
}
friend Score operator+(const Score &a, const Score &e) {
Score res;
res.node = trie.extend(a.node, e.digit);
res.val = a.val * 10 + e.digit;
return res;
}
friend bool operator<(const Score &a, const Score &b) {
if (a.node == -1)
return false;
if (b.node == -1)
return true;
if (trie.depth(a.node) != trie.depth(b.node))
return trie.depth(a.node) < trie.depth(b.node);
return trie.less(a.node, b.node);
}
friend bool operator>(const Score &a, const Score &b) { return b < a; }
friend bool operator==(const Score &a, const Score &b) { return a.node == b.node; }
friend std::istream &operator>>(std::istream &is, Score &s) { return is >> s.digit; }
};
void solve() {
LL(N, M);
Graph<Score> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, true, Score::inf()).dist;
rep(v, 1, N) print(d[v].val);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

Score は距離と辺のコストの両方に使う型です。距離としては、node がスコアの列の Trie のノード、val がそのあまりです。辺のコストとしては、digit に辺の数字を入れます。

  • operator+ は、距離に辺のコストを足す操作で、Trie を辺の数字で 1 文字進めます。
  • operator< は、列の長さ(Trie の深さ)で比べ、同じなら trie.less で辞書順に比べます。node == -1 は到達できないことを表す最大の値 inf() です。
  • operator> と operator== は、ライブラリのダイクストラ法の中で、距離の比較と未到達の判定(inf との比較)に使われます。
  • shortest_path の inf の既定値は std::numeric_limits<Cost>::max() / 4 で、この型では使えないので、Score::inf() を渡しています。
  • g.read は、重みを Cost c(1) で作ってから std::cin >> c で読むので、整数からのコンストラクタと operator>> を用意しています。始点の距離 0 は Score(0) で、Trie の根(空の列)になります。

使用ライブラリ:cpp_include@4b58304

ABC481 D - Autopilot

NN 頂点 MM 辺の有向グラフがあります。いまいる頂点から、次のどちらかの方法で移動できます。

  • 出ている辺の行き先のうち、番号が最小の頂点に燃料 00 で移動する。
  • 出ている辺の行き先を好きに選び、燃料 11 で移動する。

頂点 SS から頂点 TT へ移動するのに必要な燃料の最小値を求める問題です。到達できなければ −1-1 を出力します(2≤N≤2×1052 \le N \le 2 \times 10^5、1≤M≤2×1051 \le M \le 2 \times 10^5)。

各頂点 uu から出ている辺の行き先のうち、番号が最小の頂点へはコスト 00、それ以外の頂点へはコスト 11 の辺を張った新しいグラフを作ります。このグラフで SS から TT への最短距離が答えです。

辺のコストは 00 か 11 で非負なので、ダイクストラ法で求められます。計算量は、行き先のソートも含めて O((N+M)log⁡(N+M))O((N + M) \log (N + M)) です。コストが 00 と 11 だけなので 01-BFS でも求められ、その場合は最短路の部分が O(N+M)O(N + M) になります。

ダイクストラ法については ダイクストラ法のリンク集 も見てください。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, S, T);
S--, T--;
Graph<> g(N), h(N);
g.read(M, -1, false, true);
rep(u, N) {
vl tmp;
for (ll v : g[u])
tmp.push_back(v);
sort(tmp);
rep(i, len(tmp)) {
h.add_directed_edge(u, tmp[i], i > 0);
}
}
ll ans = shortest_path(h, S).dist[T];
print(ans > M ? -1 : ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

g.read(M, -1, false, true) は、頂点番号から 11 を引き、重みなしの有向辺として MM 本の辺を読みます。

g で頂点 u から出ている辺の行き先を tmp に集めてソートし、先頭(番号が最小の頂点)へはコスト i > 0 すなわち 00、それ以外へは 11 の辺を h に張ります。

shortest_path(h, S) は、h での S から各頂点への最短距離をダイクストラ法で求めます。到達できない頂点の距離はとても大きな値になります。到達できるときの答えは、同じ辺を 2 回使わない経路で考えれば MM 以下なので、MM より大きければ −1-1 を出力しています。

使用ライブラリ:cpp_include@4b58304

競プロキャンプ2026関西 C - Comfortable Roads

NN 個の町があり、はじめは道がありません。2 つの町を結ぶ道を追加して、どの町 ii からもすべての町へ DiD_i 本以下の道で行けるようにします。追加する道の本数の最小値を求める問題です(2≤N≤3×1052 \le N \le 3 \times 10^5、1≤Di≤N−11 \le D_i \le N - 1)。

Di=1D_i = 1 の町の個数を kk とします。

すべての町がつながっている必要があるので、道は N−1N - 1 本以上必要です。1 つの町を中心にして、残りの N−1N - 1 個の町とそれぞれ結ぶと、中心からはどの町へも 11 本で、ほかの町からはどの町へも 22 本以下で行けます。k=0k = 0 なのですべての ii で Di≥2D_i \ge 2 となり、条件を満たします。よって答えは N−1N - 1 です。

Di=1D_i = 1 の町 ii は、ほかのすべての町と直接結ばれていなければなりません。よって、Di=1D_i = 1 の町のどれかを端点に持つ道は、すべて必要です。その本数は、Di=1D_i = 1 の町と別の町の組の個数で、

(N−1)+(N−2)+⋯+(N−k)(N - 1) + (N - 2) + \dots + (N - k)

です。Di=1D_i = 1 の町を 1 つずつ見て、まだ数えていない町との組を足していくとこの式になります。

逆に、この道だけで条件を満たします。Di=1D_i = 1 の町はすべての町と直接結ばれています。それ以外の町は、Di=1D_i = 1 の町を経由してどの町へも 22 本以下で行けて、Di≥2D_i \ge 2 です。よって、これが答えです。

計算量は O(N)O(N) です。

Python
N = int(input())
D = list(map(int, input().split()))
ans = 0
k = 0
for d in D:
if d == 1:
k += 1
ans += N - k
if ans == 0:
ans += N - 1
print(ans)

Di=1D_i = 1 の町が見つかるたびに、それが何個目かを k として、N−kN - k を足しています。k≥1k \ge 1 なら ans は N−1N - 1 以上になるので、ans == 0 となるのは k=0k = 0 のときだけです。

DOJ Beginner Contest 12 D - Yet Another Hamiltonian Path Problem

頂点 1,…,N1, \dots, N の有向グラフがあり、各頂点 ii に Ai∈{0,1}A_i \in \{0, 1\} が与えられます。Ai=0A_i = 0 なら、すべての j<ij < i に対して辺 i→ji \to j があります。Ai=1A_i = 1 なら、すべての j>ij > i に対して辺 i→ji \to j があります。すべての頂点をちょうど 1 回ずつ通る経路(ハミルトン路)を 1 つ出力する問題です。存在しなければ −1-1 を出力します(2≤N≤5×1052 \le N \le 5 \times 10^5、全テストケースの NN の総和は 5×1055 \times 10^5 以下)。

Ai=0A_i = 0 の頂点を「左向き」、Ai=1A_i = 1 の頂点を「右向き」と呼びます。左向きの頂点どうしは番号の大きい順にたどれて、右向きの頂点どうしは番号の小さい順にたどれます。あとは、2 つの列をつなげられるかどうかです。

  • AN=0A_N = 0 のとき:右向きの頂点を小さい順にたどり、続けて左向きの頂点を大きい順にたどります。つなぎ目では、最後の右向きの頂点から左向きの頂点 NN に進みます。NN はどの頂点より番号が大きいので、この辺はあります。
  • A1=1A_1 = 1 のとき:左向きの頂点を大きい順にたどり、続けて右向きの頂点を小さい順にたどります。つなぎ目では、最後の左向きの頂点から右向きの頂点 11 に進みます。11 はどの頂点より番号が小さいので、この辺はあります。
  • A1=0A_1 = 0 かつ AN=1A_N = 1 のとき:頂点 11 は左向きなのに自分より小さい頂点がなく、頂点 NN は右向きなのに自分より大きい頂点がありません。どちらも出る辺がないので、経路の終点にしか置けません。終点は 1 つなので、ハミルトン路は存在しません。

計算量は O(N)O(N) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
if A[0] == 0 and A[-1] == 1:
print(-1)
continue
ans = []
if A[-1] == 0:
for i in range(N):
if A[i] == 1:
ans.append(i + 1)
for i in reversed(range(N)):
if A[i] == 0:
ans.append(i + 1)
else:
assert A[0] == 1
for i in reversed(range(N)):
if A[i] == 0:
ans.append(i + 1)
for i in range(N):
if A[i] == 1:
ans.append(i + 1)
print(*ans)

A は 0 始まりなので、頂点の番号は i + 1 です。最初の if で −1-1 の場合を除いているので、else に来たときは A1=1A_1 = 1 です。

ShareOJ Programming Contest vol.1 E - Solicitation of Murder

NN 頂点 MM 辺の有向グラフが与えられます。辺 a→ba \to b は「囚人 aa は囚人 bb に殺意を持っている」ことを表します。「生存している a,ba, b で辺 a→ba \to b があるものを選び、bb を殺す」という操作を好きな回数行ったあと、生存している囚人の集合としてありうるものの個数を 998244353998244353 で割った余りを求める問題です。

テストケースは TT 個あり、NN の総和と MM の総和はそれぞれ 2×1052 \times 10^5 以下です。

グラフを強連結成分分解します。外から入ってくる辺がない強連結成分(入次数 00 の成分)を、ここでは始点成分と呼びます。

生存者の集合 SS がありうるのは、すべての始点成分に SS の頂点が 1 つ以上あるときで、そのときに限ります。

必要性. 始点成分 CC の頂点を殺せるのは、CC の頂点だけです。CC の頂点が全員殺されたとすると、CC の中で最後に殺された頂点を殺した頂点は CC の中にいて、そのあとに殺されています。これは最後であることに反します。よって、CC には生存者が残ります。

十分性. どの頂点も、どこかの始点成分から到達できます。強連結成分の中では互いに到達できるので、すべての始点成分に SS の頂点があれば、すべての頂点が SS のどれかの頂点から到達できます。そこで、SS からの距離 d(v)d(v) を考え、SS にない頂点を d(v)d(v) が大きい順に殺します。d(v)=t≥1d(v) = t \ge 1 の頂点 vv には、d(u)=t−1d(u) = t - 1 で辺 u→vu \to v がある頂点 uu があります。uu は SS の頂点か、vv よりあとに殺す頂点なので、vv を殺すときにはまだ生きています。したがって、vv を殺せます。

条件は成分ごとに独立です。

  • 始点成分 CC では、空でない部分集合ならどれでもよいので 2∣C∣−12^{|C|} - 1 通りです。
  • それ以外の成分 CC では、制限がないので 2∣C∣2^{|C|} 通りです。

これらの積が答えです。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/graph.hpp"
#include "shogo-library/graph/graph_util.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
rep(M) {
LL(a, b);
a--, b--;
g.add_directed_edge(a, b);
}
vl dp(N);
auto tmp = strongly_connected_components(g);
mint ans = 1;
for (const auto &f : tmp) {
ll x = 0;
for (ll u : f) {
x |= dp[u];
}
ans *= mint(2).pow(f.size()) - !x;
for (ll u : f) {
for (ll v : g[u])
dp[v] = 1;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

strongly_connected_components は強連結成分をトポロジカル順に返します。dp[v] は「すでに処理した成分から vv に入る辺がある」ことを表すフラグです。成分 f を見る時点で、f に外から入る辺はすべて前の成分から来ているので、x が 00 なら f は始点成分です。成分の中の辺で立つフラグは、x を求めたあとに立てています。

使用ライブラリ:cpp_include@397a51d

牛客小白月赛138 D - Light up the Graph

頂点 nn 個、辺 mm 本の単純無向グラフがあります。各頂点は白か黒で塗られています(文字列 ss の ii 文字目が 0 なら白、1 なら黒)。

好きな頂点の集合を点灯させます(何も点灯させなくてもよい)。各頂点について、隣接する点灯した頂点の個数をその頂点の「値」とします。白い頂点の値の総和から黒い頂点の値の総和を引いたものを最大化する点灯のしかたを 1 つ出力してください(n,mn, m の総和はそれぞれ ≤2×105\le 2 \times 10^5)。

頂点 vv を点灯させるとき cv=1c_v = 1、させないとき cv=0c_v = 0 とします。uu が白なら wu=1w_u = 1、黒なら wu=−1w_u = -1 とおくと、最大化したい値は

∑uwu∑v∈N(u)cv\sum_{u} w_u \sum_{v \in N(u)} c_v

です(N(u)N(u) は uu に隣接する頂点の集合)。

この式は「白い頂点 uu から見て、隣の何個が点灯しているか」を数えています。これを「点灯した頂点 vv から見て、隣に白と黒が何個ずつあるか」に数え直します。辺 (u,v)(u, v) ごとに足しているだけなので、和の順番を入れ替えて

∑vcv∑u∈N(v)wu\sum_{v} c_v \sum_{u \in N(v)} w_u

と書けます。tv=∑u∈N(v)wut_v = \sum_{u \in N(v)} w_u(vv に隣接する白い頂点の個数から、黒い頂点の個数を引いたもの)とおくと、値は ∑vcvtv\sum_v c_v t_v です。

tvt_v は cc によらない定数なので、各頂点の cvc_v は独立に決められます。tv>0t_v > 0 なら点灯させ、tv<0t_v < 0 なら点灯させなければ最大になります。tv=0t_v = 0 の頂点は、どちらにしても値は変わりません。

点灯させた頂点の色は関係ないことに注意してください。値に効くのは隣の頂点の色だけです。

tvt_v は各頂点の隣接リストを一度ずつ見れば求まるので、計算量は O(n+m)O(n + m) です。

1 つ目のサンプルの頂点 1 は、隣が頂点 4(白)と頂点 5(黒)なので t1=0t_1 = 0 です。そのため、サンプル出力では点灯させていますが、点灯させなくても最大値 44 は変わりません。

Python
for _ in range(int(input())):
N,M=map(int,input().split())
S=input()
g=[[]for i in range(N)]
for _ in range(M):
u,v=map(int,input().split())
u,v=u-1,v-1
g[u].append(v)
g[v].append(u)
ans = []
for u in range(N):
t = 0
for v in g[u]:
if S[v] == "0":
t += 1
else:
t -= 1
if t > 0:
ans.append(u+1)
print(len(ans))
print(*ans)

各頂点 u について、隣接する白い頂点を +1+1、黒い頂点を −1-1 として足した t を求め、正なら点灯させています。点灯させる頂点が 00 個のときは print(*ans) が空行を出力するので、問題の出力形式どおりになります。

ABC477 E - Wheel Distance

頂点 1,…,N1, \ldots, N が重み AiA_i の辺で円環状につながり、さらに各頂点 ii が中心の頂点 N+1N+1 と重み BiB_i の辺でつながったグラフがあります。QQ 個のクエリ (S,T)(S, T) それぞれについて、頂点 SS から頂点 TT への最短経路の長さを求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

中心の頂点を H=N+1H = N + 1 とし、HH から各頂点への最短距離 FvF_v をダイクストラ法で求めておきます。

T=HT = H のときは、答えは FSF_S です。

T≠HT \ne H のときは、最短経路が HH を通るかどうかで場合分けします。

  • HH を通る場合: SS から HH へ行き、HH から TT へ行く経路になるので、長さは FS+FTF_S + F_T 以上です。逆に、S→HS \to H と H→TH \to T の最短経路をつなげれば長さ FS+FTF_S + F_T の経路が作れます。なので、この場合の最短は FS+FTF_S + F_T です。
  • HH を通らない場合: 円環の上だけを通るので、SS から TT へ時計回りに行くか、反時計回りに行くかの 2 通りです。AA の累積和を Gi=A1+⋯+AiG_i = A_1 + \cdots + A_i とすると、長さはそれぞれ GT−1−GS−1G_{T-1} - G_{S-1} と GN−(GT−1−GS−1)G_N - (G_{T-1} - G_{S-1}) です。

この 3 つの最小値が答えです。前処理が O(Nlog⁡N)O(N \log N)、各クエリが O(1)O(1) です。

cLay
ll@N,@Q,@A[N],@B[N],E[2N],F[N+1],G[N+1]{};int C[2N],D[2N];rep(i,N)C[i]=i,D[i]=(i+1)%N,G[i+1]=G[i]+(E[i]=A[i]),C[N+i]=i,D[N+i]=N,E[N+i]=B[i];wgraph<ll>g;g.setEdge(N+1,2N,C,D,E);g.getDist(N,F);rep(Q){ll@S--,@T--,x;if(N-T)x=F[S]+F[T],x<?=G[T]-G[S],wt(x<?=G[S]+G[N]-G[T]);else wt(F[S]);}

cLay で書いています。頂点は 0 始まりで、0,…,N−10, \ldots, N-1 が円環、NN が中心です。

C、D、E に辺の両端と重みを入れ、wgraph の setEdge で重み付き無向グラフを作り、getDist(N, F) で中心からの最短距離を F に求めています。G は AA の累積和です。

クエリでは x<?= (小さい方を代入する cLay の演算子)で 3 つの候補の最小値をとっています。N-T が 00、つまり TT が中心のときは F[S] を出力します。

Python
from heapq import heappop, heappush
from itertools import accumulate
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for i in range(N):
graph[i].append(((i + 1) % N, A[i]))
graph[(i + 1) % N].append((i, A[i]))
graph[i].append((N, B[i]))
graph[N].append((i, B[i]))
F = [None] * (N + 1)
pq = [(0, N)]
while pq:
d, v = heappop(pq)
if F[v] is not None:
continue
F[v] = d
for u, w in graph[v]:
if F[u] is None:
heappush(pq, (d + w, u))
acc = [0, *accumulate(A)]
ans = []
for _ in range(Q):
S, T = map(int, input().split())
S -= 1
T -= 1
if T == N:
ans.append(F[S])
else:
ans.append(min(F[S] + F[T], acc[T] - acc[S], acc[S] + acc[N] - acc[T]))
print(*ans, sep="\n")

cLay 版と同じ処理です。ダイクストラ法は heapq で書いています。

ABC478 E - lt and le

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