結果
問題 | No.1778 括弧列クエリ / Bracketed Sequence Query |
ユーザー | Wizist |
提出日時 | 2021-12-11 20:45:48 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 528 ms / 2,000 ms |
コード長 | 1,657 bytes |
コンパイル時間 | 1,828 ms |
コンパイル使用メモリ | 178,176 KB |
実行使用メモリ | 35,856 KB |
最終ジャッジ日時 | 2023-09-27 09:21:52 |
合計ジャッジ時間 | 10,458 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 60 ms
4,376 KB |
testcase_01 | AC | 61 ms
4,376 KB |
testcase_02 | AC | 61 ms
4,380 KB |
testcase_03 | AC | 53 ms
4,376 KB |
testcase_04 | AC | 63 ms
4,380 KB |
testcase_05 | AC | 107 ms
12,084 KB |
testcase_06 | AC | 45 ms
4,884 KB |
testcase_07 | AC | 10 ms
7,736 KB |
testcase_08 | AC | 317 ms
26,340 KB |
testcase_09 | AC | 28 ms
10,832 KB |
testcase_10 | AC | 116 ms
20,896 KB |
testcase_11 | AC | 85 ms
14,656 KB |
testcase_12 | AC | 113 ms
12,192 KB |
testcase_13 | AC | 303 ms
25,708 KB |
testcase_14 | AC | 104 ms
18,720 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 300 ms
26,544 KB |
testcase_17 | AC | 320 ms
26,432 KB |
testcase_18 | AC | 305 ms
26,428 KB |
testcase_19 | AC | 298 ms
26,336 KB |
testcase_20 | AC | 315 ms
26,516 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,376 KB |
testcase_23 | AC | 493 ms
20,628 KB |
testcase_24 | AC | 528 ms
24,924 KB |
testcase_25 | AC | 517 ms
25,068 KB |
testcase_26 | AC | 380 ms
35,856 KB |
testcase_27 | AC | 130 ms
35,752 KB |
ソースコード
// No.1778 括弧列クエリ / Bracketed Sequence Query #include <bits/stdc++.h> using namespace std; struct LCA { vector<vector<int>> anc; // [power][node] vector<int> dist, t; LCA(const vector<vector<int>> &e, int root = 0) : dist(e.size()) { anc.assign(32 - __builtin_clz(e.size()), vector<int>(e.size())); function<void(int, int)> dfs = [&](int u, int p) { anc[0][u] = max(p, 0); t.push_back(u); for (auto v : e[u]) if (v != p) dist[v] = dist[u] + 1, dfs(v, u); }; dfs(root, -1); for (int k = 1; k < anc.size(); k++) for (int i = 0; i < anc[k].size(); i++) anc[k][i] = anc[k - 1][anc[k - 1][i]]; } int operator()(int u, int v) { if (dist[u] < dist[v]) swap(u, v); for (int k = anc.size() - 1, b = dist[u] - dist[v]; k >= 0; k--) if (b & (1 << k)) u = anc[k][u]; for (int k = anc.size() - 1; k >= 0; k--) if (anc[k][u] != anc[k][v]) u = anc[k][u], v = anc[k][v]; return u == v ? u : anc[0][u]; } }; int main(int argc, char *argv[]) { cin.tie(0)->sync_with_stdio(0); int n, q; string s; cin >> n >> q >> s; s = "(" + s + ")"; n += 1; vector<int> p(n), st; for (int i = 0; i < n; i++) if (s[i] == '(') st.push_back(i); else p[i] = st.back(), p[st.back()] = i, st.pop_back(); vector<vector<int>> g(n); function<void(int, int)> build = [&](int u, int c) { if (c <= 2) return; for (int v = u + 1; v < u + c && p[v] > v; v = p[v] + 1) g[u].push_back(v), build(v, p[v] - v + 1); }; build(0, n); auto lca = LCA(g); while (q--) { int x, y; cin >> x >> y; auto t = lca(min(x, p[x]), min(y, p[y])); if (t == 0) cout << -1 << "\n"; else cout << t << ' ' << p[t] << "\n"; } return 0; }