[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-i

6. できあがった文字列を、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;
}

https://atcoder.jp/contests/arc030/submissions/30945302