結果
問題 | No.1914 Directed by Two Sequences |
ユーザー | tokusakurai |
提出日時 | 2022-04-11 11:39:30 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 513 ms / 3,000 ms |
コード長 | 7,809 bytes |
コンパイル時間 | 4,105 ms |
コンパイル使用メモリ | 235,208 KB |
実行使用メモリ | 19,220 KB |
最終ジャッジ日時 | 2023-08-22 06:37:35 |
合計ジャッジ時間 | 23,237 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 113 ms
8,216 KB |
testcase_03 | AC | 117 ms
8,272 KB |
testcase_04 | AC | 113 ms
8,244 KB |
testcase_05 | AC | 113 ms
8,296 KB |
testcase_06 | AC | 117 ms
8,232 KB |
testcase_07 | AC | 159 ms
8,148 KB |
testcase_08 | AC | 115 ms
8,128 KB |
testcase_09 | AC | 121 ms
8,160 KB |
testcase_10 | AC | 228 ms
16,164 KB |
testcase_11 | AC | 232 ms
11,792 KB |
testcase_12 | AC | 233 ms
13,008 KB |
testcase_13 | AC | 236 ms
16,500 KB |
testcase_14 | AC | 228 ms
11,780 KB |
testcase_15 | AC | 234 ms
13,048 KB |
testcase_16 | AC | 232 ms
13,236 KB |
testcase_17 | AC | 230 ms
11,488 KB |
testcase_18 | AC | 248 ms
12,892 KB |
testcase_19 | AC | 167 ms
11,996 KB |
testcase_20 | AC | 169 ms
9,644 KB |
testcase_21 | AC | 222 ms
11,336 KB |
testcase_22 | AC | 234 ms
15,580 KB |
testcase_23 | AC | 236 ms
11,868 KB |
testcase_24 | AC | 255 ms
12,832 KB |
testcase_25 | AC | 288 ms
10,968 KB |
testcase_26 | AC | 291 ms
10,748 KB |
testcase_27 | AC | 272 ms
11,132 KB |
testcase_28 | AC | 264 ms
10,948 KB |
testcase_29 | AC | 283 ms
10,936 KB |
testcase_30 | AC | 277 ms
10,964 KB |
testcase_31 | AC | 463 ms
16,340 KB |
testcase_32 | AC | 232 ms
19,220 KB |
testcase_33 | AC | 224 ms
9,224 KB |
testcase_34 | AC | 513 ms
18,180 KB |
testcase_35 | AC | 236 ms
11,220 KB |
testcase_36 | AC | 408 ms
16,244 KB |
testcase_37 | AC | 383 ms
15,992 KB |
testcase_38 | AC | 454 ms
16,936 KB |
testcase_39 | AC | 453 ms
17,408 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename Monoid> struct Segment_Tree { using F = function<Monoid(Monoid, Monoid)>; int n; vector<Monoid> seg; const F f; const Monoid e1; // f(f(a,b),c) = f(a,f(b,c)), f(e1,a) = f(a,e1) = a Segment_Tree(const vector<Monoid> &v, const F &f, const Monoid &e1) : f(f), e1(e1) { int m = v.size(); n = 1; while (n < m) n <<= 1; seg.assign(2 * n, e1); copy(begin(v), end(v), seg.begin() + n); for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]); } Segment_Tree(int m, const Monoid &x, const F &f, const Monoid &e1) : f(f), e1(e1) { n = 1; while (n < m) n <<= 1; seg.assign(2 * n, e1); vector<Monoid> v(m, x); copy(begin(v), end(v), begin(seg) + n); for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]); } void change(int i, const Monoid &x, bool update = true) { if (update) { seg[i + n] = x; } else { seg[i + n] = f(seg[i + n], x); } i += n; while (i >>= 1) seg[i] = f(seg[2 * i], seg[2 * i + 1]); } Monoid query(int l, int r) const { Monoid L = e1, R = e1; l += n, r += n; while (l < r) { if (l & 1) L = f(L, seg[l++]); if (r & 1) R = f(seg[--r], R); l >>= 1, r >>= 1; } return f(L, R); } Monoid operator[](int i) const { return seg[n + i]; } template <typename C> int find_subtree(int i, const C &check, const Monoid &x, Monoid &M, int type) const { while (i < n) { Monoid nxt = type ? f(seg[2 * i + type], M) : f(M, seg[2 * i + type]); if (check(nxt, x)) { i = 2 * i + type; } else { M = nxt; i = 2 * i + (type ^ 1); } } return i - n; } template <typename C> int find_first(int l, const C &check, const Monoid &x) const { // check((区間 [l,r] での演算結果), x) を満たす最小の r Monoid L = e1; int a = l + n, b = n + n; while (a < b) { if (a & 1) { Monoid nxt = f(L, seg[a]); if (check(nxt, x)) return find_subtree(a, check, x, L, 0); L = nxt, a++; } a >>= 1, b >>= 1; } return n; } template <typename C> int find_last(int r, const C &check, const Monoid &x) const { // check((区間 [l,r) での演算結果), x) を満たす最大の l Monoid R = e1; int a = n, b = r + n; while (a < b) { if ((b & 1) || a == 1) { Monoid nxt = f(seg[--b], R); if (check(nxt, x)) return find_subtree(b, check, x, R, 1); R = nxt; } a >>= 1, b >>= 1; } return -1; } }; int main() { int N, M; cin >> N >> M; vector<int> A(N), B(N); for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < N; i++) cin >> B[i]; set<pair<int, int>> ng; // 切られている辺 for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; u--, v--; ng.emplace(u, v); } // 補グラフを DFS して強連結成分分解する : O((N + M)(log(N) + log(M))) auto f = [](int a, int b) { return max(a, b); }; auto c = [](int a, int b) { return a > b; }; const int inf = (1 << 30) - 1; Segment_Tree<int> seg1(A, f, -inf), seg2(B, f, -inf); vector<int> vs; vector<int> comp(N, -1); function<void(int)> dfs = [&](int now) { if (comp[now] != -1) return; comp[now] = 1; seg1.change(now, -inf), seg2.change(now, -inf); int p = now + 1; while (p < N) { int np = seg2.find_first(p, c, A[now]); if (np >= N) break; if (!ng.count(make_pair(now, np))) dfs(np); p = np + 1; } p = now; while (p > 0) { int np = seg1.find_last(p, c, B[now]); if (np < 0) break; if (!ng.count(make_pair(np, now))) dfs(np); p = np; } vs.emplace_back(now); }; function<void(int, int)> rdfs = [&](int now, int col) { if (comp[now] != -1) return; comp[now] = col; seg1.change(now, -inf), seg2.change(now, -inf); int p = now + 1; while (p < N) { int np = seg2.find_first(p, c, -A[now]); if (np >= N) break; if (!ng.count(make_pair(now, np))) rdfs(np, col); p = np + 1; } p = now; while (p > 0) { int np = seg1.find_last(p, c, -B[now]); if (np < 0) break; if (!ng.count(make_pair(np, now))) rdfs(np, col); p = np; } }; for (int i = 0; i < N; i++) { if (comp[i] == -1) dfs(i); } fill(begin(comp), end(comp), -1); reverse(begin(vs), end(vs)); for (int i = 0; i < N; i++) seg1.change(i, -A[i]), seg2.change(i, -B[i]); int K = 0; for (auto &i : vs) { if (comp[i] == -1) rdfs(i, K++); } vector<vector<int>> ids(K); for (int i = 0; i < N; i++) ids[comp[i]].emplace_back(i); // トポロジカルソートの逆順に見て必要な辺を調べる : O((N + M)(log(N) + log(M)) + M√M) vector<vector<int>> es(K); vector<int> deg(K, 0); set<int> rem; for (int i = 0; i < N; i++) seg1.change(i, -inf), seg2.change(i, -inf); for (int i = K - 1; i >= 0; i--) { queue<int> que; for (auto &e : rem) que.emplace(e); vector<int> check; for (auto &u : ids[i]) seg1.change(u, -A[u]), seg2.change(u, -B[u]); while (!empty(que)) { int j = que.front(); que.pop(); bool flag = false; // 強連結成分 i から強連結成分 j への辺があるかの判定 for (auto &v : ids[j]) { int p = v + 1; while (p < N) { int np = seg2.find_first(p, c, -A[v]); if (np >= N) break; if (!ng.count(make_pair(v, np))) { flag = true; break; } p = np + 1; } if (flag) break; p = v; while (p > 0) { int np = seg1.find_last(p, c, -B[v]); if (np < 0) break; if (!ng.count(make_pair(np, v))) { flag = true; break; } p = np; } if (flag) break; } if (flag) { if (rem.count(j)) rem.erase(j); es[i].emplace_back(j); } else { check.emplace_back(j); for (auto &e : es[j]) { if (--deg[e] == 0) que.emplace(e); } } } check.emplace_back(i); for (auto &j : check) { for (auto &e : es[j]) deg[e]++; } rem.emplace(i); for (auto &u : ids[i]) seg1.change(u, -inf), seg2.change(u, -inf); } vector<pair<int, int>> ans; for (int i = 0; i < K; i++) { int L = ids[i].size(); if (L > 1) { for (int j = 0; j < L; j++) { int u = ids[i][j], v = ids[i][(j + 1) % L]; ans.emplace_back(u, v); } } for (auto &j : es[i]) ans.emplace_back(ids[i][0], ids[j][0]); } cout << ans.size() << '\n'; for (auto [u, v] : ans) cout << u + 1 << ' ' << v + 1 << '\n'; }