結果
問題 | No.1778 括弧列クエリ / Bracketed Sequence Query |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-07 00:09:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 3,680 bytes |
コンパイル時間 | 4,550 ms |
コンパイル使用メモリ | 122,388 KB |
最終ジャッジ日時 | 2025-01-26 06:11:09 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; using u32 = uint32_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(n); i++) struct HLD { private: int N; vector<int> P; vector<int> PP; vector<int> PD; vector<int> D; public: vector<int> rangeL; vector<int> rangeR; HLD(const vector<vector<int>>& E = { {} }) { N = E.size(); P.assign(N, -1); vector<int> I = { 0 }; rep(i, I.size()) { int p = I[i]; for (int e : E[p]) if (P[p] != e) { I.push_back(e); P[e] = p; } } vector<int> Z(N, 1); for (int i = N - 1; i >= 1; i--) Z[P[I[i]]] += Z[I[i]]; PP.resize(N); for (int i = 0; i < N; i++) PP[i] = i; vector<int> nx(N, -1); for (int p : I) if (p != 0) { if (nx[P[p]] == -1) nx[P[p]] = p; if (Z[nx[P[p]]] < Z[p]) nx[P[p]] = p; } rep(i, N) if (nx[i] != -1) PP[nx[i]] = i; for (int p : I) if (p != 0) PP[p] = PP[PP[p]]; PD.assign(N, N); PD[0] = 0; for (int p : I) if (p != 0) PD[p] = min(PD[PP[p]], PD[P[p]] + 1); D.assign(N, 0); for (int p : I) D[p] = (p == 0) ? 0 : (D[P[p]] + 1); rangeL.assign(N, -1); rangeR.assign(N, -1); vector<int> dfs; int ir = 0; dfs.push_back(0); while (dfs.size()) { int p = dfs.back(); dfs.pop_back(); if (p < 0) { rangeR[-1 - p] = ir; continue; } dfs.push_back(-1 - p); for (int e : E[p]) if (P[p] != e) if (e != nx[p]) dfs.push_back(e); if (nx[p] != -1) dfs.push_back(nx[p]); rangeL[p] = ir++; } } int lca(int u, int v) { if (PD[u] < PD[v]) swap(u, v); while (PD[u] > PD[v]) u = P[PP[u]]; while (PP[u] != PP[v]) { u = P[PP[u]]; v = P[PP[v]]; } return (D[u] > D[v]) ? v : u; } vector<pair<int, int>> getpath(int r, int c) { vector<pair<int, int>> res; while (PD[r] < PD[c]) { res.push_back({ rangeL[PP[c]], rangeL[c] + 1 }); c = P[PP[c]]; } if (PP[r] != PP[c]) return {}; if (D[r] > D[c]) return {}; res.push_back({ rangeL[r], rangeL[c] + 1 }); reverse(res.begin(), res.end()); return move(res); } }; int N,Q; string S; vector<vector<int>> E; vector<int> eachother; vector<int> vtx_idx; vector<int> open_pos; int num_vtx; HLD hld; int main() { cin >> N >> Q; cin >> S; S = "(" + S + ")"; N += 2; eachother.assign(N, -1); vtx_idx.assign(N, -1); vector<int> open_stack; num_vtx = 0; rep(i,S.size()){ if(S[i] == '('){ vtx_idx[i] = num_vtx; E.push_back({}); if(!open_stack.empty()) E[vtx_idx[open_stack.back()]].push_back(vtx_idx[i]); num_vtx++; open_stack.push_back(i); open_pos.push_back(i); } else if(S[i] == ')'){ int p = open_stack.back(); open_stack.pop_back(); eachother[i] = p; eachother[p] = i; vtx_idx[i] = vtx_idx[p]; } } hld = HLD(E); rep(i,Q){ int x,y; cin >> x >> y; int h = hld.lca(vtx_idx[x], vtx_idx[y]); int ans = open_pos[h]; if(ans == 0){ cout << "-1\n"; } else{ cout << ans << " " << eachother[ans] << "\n"; } } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;