[ARC30] C - 有向グラフ
[Q] https://atcoder.jp/contests/arc030/tasks/arc030_3
アウトラインはすぐ決まるけど、実装とても重い。
考察
1. SCC(強連結成分分解)して、グループ化したグラフを作成する。
2. 閉路は好きな順番で文字を採用できる。sortしておく。
3. 解答文字を作ろうと思う。
4. 入次数(indeg) = 0 の頂点からスタートしてdfs。
5. 経由するグループの文字列をどんどん結合。
ab h
\ /
cefg
/ \
d i
4. 左から右に流れるとして、
indeg[0] = {ab, d}
5. dfsする
6. 次の文字列ができうる。
ab-cefg-h
ab-cefg-i
d-cefg-h
d-cefg-i6. できあがった文字列を、K文字にするときに、辞書順で最小にする。
7. 辞書順にするのはseg_tree。
S = "cbacba"
K=2のとき、
aa
になるべき。
・1文字目
2文字採用したいので、0~5文字の中から絶対1つ選ばないと満たされない
"cbacba"
~~~~~
seg(0, 5)の最小文字はa
なので、aを採用。
・2文字目
cbacba
|~~~
さっきS[2]='a'をとったので、index3以降で選ぶ。
これが最終文字なので、3~6文字の中から1つ選べばいい。
seg(3, 6) = 'a'
でaを採用。
K=2のとき、aa になる実装
vector<vector<int>> topo(500000, vector<int>(0, 0));
ll N, M, K;
char C[303];
ll indeg[303];
vector<ll> G[505]; // origin
vector<ll> NG[505]; // after SCC
string S[505]; // after SCC
string ans;
struct union_tree {
vector<ll> par;
union_tree(ll N) {
par.reserve(N);
rep(i, N) par.emplace_back(i);
}
ll root(ll u) {
if (par[u] == u) return u;
return par[u] = root(par[u]);
}
void unite(ll u, ll v) {
ll ru = root(u);
ll rv = root(v);
if (ru > rv) swap(ru, rv);
par[rv] = ru;
}
};
// K文字の辞書順にする
void resize_K(string &s) {
ll N = s.size();
if (N < K) return;
RangeMin Z;
Z.init(N);
rep(i, N) Z.update(i, s[i]);
string T;
ll L = 0;
ll R = N - K;
rep(i, K) {
++R;
char low = Z.query(L, R);
T += low;
while (s[L] != low) ++L;
++L;
}
chmin(ans, T);
}
// 解答文字列作る
void dfs(ll v, string s, union_tree &tree) {
s += S[tree.root(v)];
if (NG[v].empty()) {
resize_K(s); // update ans
return;
}
for (auto u : NG[v]) {
dfs(u, s, tree);
}
}
int main() {
cincout();
cin >> N >> M >> K;
rep(i, N) cin >> C[i];
SCC scc(N);
rep(i, M) {
int A, B;
cin >> A >> B;
--A, --B;
G[A].emplace_back(B);
scc.add_edge(A, B);
++indeg[B];
}
int scc_num = scc.solve();
scc.make_graph();
// cerr << "scc_num:" << scc_num << endl; // ループグループの数
union_tree tree(N);
for (int i = scc_num - 1; i >= 0; i--) {
auto &t0 = topo[i][0];
ll tsz = topo[i].size();
string T;
rep(j, tsz) {
auto &tj = topo[i][j];
tree.unite(t0, tj);
T += C[tj];
}
sort(all(T));
S[tree.root(t0)] = T;
}
// NewG 強連結のグラフに作り替える
rep(i, N) {
for (auto u : G[i]) {
if (tree.root(i) == tree.root(u)) continue;
NG[tree.root(i)].emplace_back(tree.root(u));
}
}
// indeg==0を探す
queue<ll> starts;
rep(i, N) {
if (indeg[i] == 0) starts.push(i);
}
if (starts.empty()) starts.push(0);
ans.assign(K + 1, 'z');
// dfsして文字列作って、K文字の辞書順にする
while (!starts.empty()) {
auto q = starts.front();
starts.pop();
dfs(q, "", tree);
}
if (ans.size() != K) {
ans = "-1";
}
cout << ans << endl;
}