結果
問題 | No.2342 Triple Tree Query (Hard) |
ユーザー | 👑 Nachia |
提出日時 | 2023-06-03 00:16:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 345 ms / 10,000 ms |
コード長 | 20,700 bytes |
コンパイル時間 | 1,789 ms |
コンパイル使用メモリ | 120,376 KB |
実行使用メモリ | 28,420 KB |
最終ジャッジ日時 | 2024-06-09 02:39:05 |
合計ジャッジ時間 | 11,340 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 4 ms
5,376 KB |
testcase_03 | AC | 5 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 4 ms
5,376 KB |
testcase_06 | AC | 5 ms
5,376 KB |
testcase_07 | AC | 220 ms
28,236 KB |
testcase_08 | AC | 225 ms
28,168 KB |
testcase_09 | AC | 214 ms
28,292 KB |
testcase_10 | AC | 226 ms
28,260 KB |
testcase_11 | AC | 241 ms
28,288 KB |
testcase_12 | AC | 214 ms
28,292 KB |
testcase_13 | AC | 216 ms
28,340 KB |
testcase_14 | AC | 219 ms
28,240 KB |
testcase_15 | AC | 226 ms
28,228 KB |
testcase_16 | AC | 227 ms
28,292 KB |
testcase_17 | AC | 259 ms
28,388 KB |
testcase_18 | AC | 254 ms
28,220 KB |
testcase_19 | AC | 255 ms
28,292 KB |
testcase_20 | AC | 248 ms
28,244 KB |
testcase_21 | AC | 247 ms
28,296 KB |
testcase_22 | AC | 108 ms
28,284 KB |
testcase_23 | AC | 107 ms
28,248 KB |
testcase_24 | AC | 105 ms
28,292 KB |
testcase_25 | AC | 337 ms
28,220 KB |
testcase_26 | AC | 332 ms
28,208 KB |
testcase_27 | AC | 334 ms
28,288 KB |
testcase_28 | AC | 332 ms
28,420 KB |
testcase_29 | AC | 345 ms
28,212 KB |
testcase_30 | AC | 116 ms
28,260 KB |
testcase_31 | AC | 112 ms
28,220 KB |
testcase_32 | AC | 116 ms
28,292 KB |
testcase_33 | AC | 159 ms
28,304 KB |
testcase_34 | AC | 164 ms
28,236 KB |
testcase_35 | AC | 163 ms
28,292 KB |
testcase_36 | AC | 177 ms
28,216 KB |
testcase_37 | AC | 165 ms
28,288 KB |
ソースコード
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\nyaanio.hpp" #include <cstring> #include <type_traits> #include <utility> #include <cstdio> #include <string> #include <cstdint> namespace fastio { static constexpr int SZ = 1 << 17; char inbuf[SZ], outbuf[SZ]; int in_left = 0, in_right = 0, out_right = 0; struct Pre { char num[40000]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr pre; inline void load() { int len = in_right - in_left; memmove(inbuf, inbuf + in_left, len); in_right = len + fread(inbuf + len, 1, SZ - len, stdin); in_left = 0; if(in_right != SZ) inbuf[in_right] = '\000'; } inline void flush() { fwrite(outbuf, 1, out_right, stdout); out_right = 0; } inline void skip_space() { if (in_left + 32 > in_right) load(); while (inbuf[in_left] <= ' ') in_left++; } inline void rd(char& c) { if (in_left + 32 > in_right) load(); c = inbuf[in_left++]; } template <typename T> inline void rd(T& x) { if (in_left + (int)sizeof(T) * 8 > in_right) load(); char c; do c = inbuf[in_left++]; while (c < '-'); [[maybe_unused]] bool minus = false; if constexpr (std::is_signed<T>::value == true) { if (c == '-') minus = true, c = inbuf[in_left++]; } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = inbuf[in_left++]; } if constexpr (std::is_signed<T>::value == true) { if (minus) x = -x; } } inline void wt(char c) { if (out_right > SZ - 32) flush(); outbuf[out_right++] = c; } inline void wt(bool b) { if (out_right > SZ - 32) flush(); outbuf[out_right++] = b ? '1' : '0'; } inline void wt(const std::string &s) { if (out_right + s.size() > SZ - 32) flush(); if (s.size() > SZ - 32){ fwrite(s.c_str(), 1, s.size(), stdout); return; } memcpy(outbuf + out_right, s.data(), sizeof(char) * s.size()); out_right += s.size(); } inline void wt(const char* s) { wt(std::string(s)); } template <typename T> inline void wt(T x) { if (out_right > SZ - (int)sizeof(T) * 8) flush(); if (!x) { outbuf[out_right++] = '0'; return; } if constexpr (std::is_signed<T>::value == true) { if (x < 0) outbuf[out_right++] = '-', x = -x; } constexpr int SZT = sizeof(T) * 8; int i = SZT - 4; char buf[SZT]; while (x >= 10000) { memcpy(buf + i, pre.num + (x % 10000) * 4, 4); x /= 10000; i -= 4; } if (x < 100) { if (x < 10) { outbuf[out_right] = '0' + x; ++out_right; } else { uint32_t q = (uint32_t(x) * 205) >> 11; uint32_t r = uint32_t(x) - q * 10; outbuf[out_right] = '0' + q; outbuf[out_right + 1] = '0' + r; out_right += 2; } } else { if (x < 1000) { memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3); out_right += 3; } else { memcpy(outbuf + out_right, pre.num + (x << 2), 4); out_right += 4; } } memcpy(outbuf + out_right, buf + i + 4, SZT - 4 - i); out_right += SZT - 4 - i; } } // namespace fastio namespace nachia{ struct CInStream{} cin; template <typename T> inline CInStream& operator>>(CInStream& c, T& dest){ fastio::rd(dest); return c; } struct COutStream{ ~COutStream(){ atexit(fastio::flush); } } cout; template <typename T> inline COutStream& operator<<(COutStream& c, const T& src){ fastio::wt(src); return c; } } // namespace nachia #line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\csr-array.hpp" #include <vector> #include <algorithm> namespace nachia{ template<class Elem> class CsrArray{ public: struct ListRange{ using iterator = typename std::vector<Elem>::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector<Elem>::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector<Elem> m_list; std::vector<int> m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){ CsrArray res; res.m_n = n; std::vector<int> buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\graph.hpp" #include <cassert> #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\graph.hpp" namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } }; using Base = std::vector<std::pair<int, int>>; Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} Graph(int n, const std::vector<std::pair<int, int>>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i<edges.size(); i++) m_e[i] = { edges[i].first, edges[i].second }; } template<class Cin> static Graph Input(Cin& cin, int n, bool undirected, int m, bool offset = 0){ Graph res(n, undirected, m); for(int i=0; i<m; i++){ int u, v; cin >> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector<int>& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i<numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV); for(auto& e : m_e){ e.from = mapping[e.from]; e.to = mapping[e.to]; } m_n = newV; } std::vector<Graph> induce(int num, const std::vector<int>& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i<n; i++) assert(-1 <= mapping[i] && mapping[i] < num); std::vector<int> indexV(n), newV(num); for(int i=0; i<n; i++) if(mapping[i] >= 0) indexV[i] = newV[mapping[i]]++; std::vector<Graph> res; res.reserve(num); for(int i=0; i<num; i++) res.emplace_back(newV[i], isUndirected()); for(auto e : m_e) if(mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray<int> getEdgeIndexArray(bool undirected) const { std::vector<std::pair<int, int>> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i<numEdges(); i++){ auto e = operator[](i); src.emplace_back(e.from, i); if(undirected) src.emplace_back(e.to, i); } return CsrArray<int>::Construct(numVertices(), src); } CsrArray<int> getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray<int> getAdjacencyArray(bool undirected) const { std::vector<std::pair<int, int>> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray<int>::Construct(numVertices(), src); } CsrArray<int> getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector<Edge> m_e; bool m_isUndir; }; } // namespace nachia #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\tree\\heavy-light-decomposition.hpp" namespace nachia{ struct HeavyLightDecomposition{ private: int N; std::vector<int> P; std::vector<int> PP; std::vector<int> PD; std::vector<int> D; std::vector<int> I; std::vector<int> rangeL; std::vector<int> rangeR; public: HeavyLightDecomposition(const CsrArray<int>& E = CsrArray<int>::Construct(1, {}), int root = 0){ N = E.size(); P.assign(N, -1); I = {root}; I.reserve(N); for(int i=0; i<(int)I.size(); i++){ int p = I[i]; for(int e : E[p]) if(P[p] != e){ I.push_back(e); P[e] = p; } } std::vector<int> Z(N, 1); std::vector<int> nx(N, -1); PP.resize(N); for(int i=0; i<N; i++) PP[i] = i; for(int i=N-1; i>=1; i--){ int p = I[i]; Z[P[p]] += Z[p]; if(nx[P[p]] == -1) nx[P[p]] = p; if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p; } for(int p : I) if(nx[p] != -1) PP[nx[p]] = p; PD.assign(N,N); PD[root] = 0; D.assign(N,0); for(int p : I) if(p != root){ PP[p] = PP[PP[p]]; PD[p] = std::min(PD[PP[p]], PD[P[p]]+1); D[p] = D[P[p]]+1; } rangeL.assign(N,0); rangeR.assign(N,0); for(int p : I){ rangeR[p] = rangeL[p] + Z[p]; int ir = rangeR[p]; for(int e : E[p]) if(P[p] != e) if(e != nx[p]){ rangeL[e] = (ir -= Z[e]); } if(nx[p] != -1){ rangeL[nx[p]] = rangeL[p] + 1; } } I.resize(N); for(int i=0; i<N; i++) I[rangeL[i]] = i; } HeavyLightDecomposition(const Graph& tree, int root = 0) : HeavyLightDecomposition(tree.getAdjacencyArray(true), root) {} int numVertices() const { return N; } int depth(int p) const { return D[p]; } int toSeq(int vertex) const { return rangeL[vertex]; } int toVtx(int seqidx) const { return I[seqidx]; } int toSeq2In(int vertex) const { return rangeL[vertex] * 2 - D[vertex]; } int toSeq2Out(int vertex) const { return rangeR[vertex] * 2 - D[vertex] - 1; } int parentOf(int v) const { return P[v]; } int heavyRootOf(int v) const { return PP[v]; } int heavyChildOf(int v) const { if(toSeq(v) == N-1) return -1; int cand = toVtx(toSeq(v) + 1); if(PP[v] == PP[cand]) return cand; return -1; } int lca(int u, int v) const { if(PD[u] < PD[v]) std::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; } int dist(int u, int v) const { return depth(u) + depth(v) - depth(lca(u,v)) * 2; } std::vector<std::pair<int,int>> path(int r, int c, bool include_root = true, bool reverse_path = false) const { if(PD[c] < PD[r]) return {}; std::vector<std::pair<int,int>> res(PD[c]-PD[r]+1); for(int i=0; i<(int)res.size()-1; i++){ res[i] = std::make_pair(rangeL[PP[c]], rangeL[c]+1); c = P[PP[c]]; } if(PP[r] != PP[c] || D[r] > D[c]) return {}; res.back() = std::make_pair(rangeL[r]+(include_root?0:1), rangeL[c]+1); if(res.back().first == res.back().second) res.pop_back(); if(!reverse_path) std::reverse(res.begin(),res.end()); else for(auto& a : res) a = std::make_pair(N - a.second, N - a.first); return res; } std::pair<int,int> subtree(int p){ return std::make_pair(rangeL[p], rangeR[p]); } int median(int x, int y, int z) const { return lca(x,y) ^ lca(y,z) ^ lca(x,z); } int la(int from, int to, int d) const { if(d < 0) return -1; int g = lca(from,to); int dist0 = D[from] - D[g] * 2 + D[to]; if(dist0 < d) return -1; int p = from; if(D[from] - D[g] < d){ p = to; d = dist0 - d; } while(D[p] - D[PP[p]] < d){ d -= D[p] - D[PP[p]] + 1; p = P[PP[p]]; } return I[rangeL[p] - d]; } }; } // namespace nachia #line 1 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\dual-segment-tree.hpp" #line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\dual-segment-tree.hpp" namespace nachia{ template< class F, F composition(F f, F x) > struct DualSegtree { struct Node { F f; bool propagated; }; int N; int logN; std::vector<Node> A; void mapf(Node& a, F f) { a.propagated = false; a.f = composition(f, a.f); } void spread(int i) { if(A[i].propagated || !(i < N)) return; mapf(A[i*2], A[i].f); mapf(A[i*2+1], A[i].f); A[i] = A[0]; } DualSegtree(int n, F id) { N=1; logN=0; while(N<n){ N *= 2; logN++; } A.assign(N*2, { id, true }); } DualSegtree(const std::vector<F>& a) : DualSegtree(a.size()) { for(int i=0; i<a.size(); i++){ A[i+N].f = a[i]; A[i+N].propagated = false; } } void clear(int p) { p += N; for(int d=logN; d; d--) spread(p >> d); A[p] = A[0]; } F get(int p){ p += N; for(int d=logN; d; d--) spread(p >> d); return A[p].f; } void apply(int l, int r, F f){ if(!(l < r)) return; if(l == 0 && r == N){ mapf(A[1], f); return; } l += N; r += N; for(int d=logN; d; d--){ if((l >> d) << d != l) spread(l >> d); if((r >> d) << d != r) spread(r >> d); } while(l < r){ if(l&1){ mapf(A[l++], f); } l /= 2; if(r&1){ mapf(A[--r], f); } r /= 2; } } void apply(int p, F f){ p += N; for(int d=logN; d; d--) spread(p >> d); mapf(A[p], f); } }; } // namespace nachia; #line 6 "..\\Main.cpp" #include <tuple> #include <atcoder/modint> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; struct Affine { Modint c, d; static Affine Construct(int c, int d){ return Affine{ Modint::raw(c), Modint::raw(d) }; } Modint eval(Modint x) const { return c*x+d; } }; Affine f1(Affine a, Affine b){ Affine res; res.c = a.c * b.c; res.d = a.c * b.d + a.d; return res; } int main(){ using nachia::cin; using nachia::cout; int maxK = 10; int N, Q; cin >> N >> Q; auto tree = nachia::Graph::Input(cin, N, true, N-1, 1); auto hld = nachia::HeavyLightDecomposition(tree); tree = nachia::Graph(N, false); rep(i,N) if(hld.parentOf(i) >= 0) tree.addEdge(hld.parentOf(i), i); auto adj = tree.getAdjacencyArray(); vector<int> h11(N); rep(i,N) h11[i] = (hld.depth(i) <= maxK) ? -1 : hld.toSeq(hld.la(i, 0, maxK+1)); vector<int> ord(N); rep(i,N) ord[i] = i; sort(ord.begin(), ord.end(), [&](int a, int b){ return make_tuple(h11[a], hld.depth(a), hld.toSeq(a)) < make_tuple(h11[b], hld.depth(b), hld.toSeq(b)); }); vector<int> pos(N); rep(i,N) pos[ord[i]] = i; vector<int> hdepth(N); rep(i,N) hdepth[i] = hld.depth(i) - hld.depth(hld.heavyRootOf(i)); auto isOnHeavy = [&](int v){ return hdepth[v] > maxK; }; vector<vector<pair<int, int>>> seq(N, vector<pair<int,int>>(maxK+1, {N,0})); rep(v,N){ int w = v; int p = pos[v]; for(int k=0; k<=maxK; k++){ seq[w][k].first = min(seq[w][k].first, p); seq[w][k].second = max(seq[w][k].second, p+1); w = hld.parentOf(w); if(w < 0) break; } } rep(i,N) for(auto& a : seq[i]) if(a.first >= a.second) a = {0,0}; vector<int> h11pos(N+1, 0); rep(i,N) h11pos[h11[ord[i]]+1] = i+1; rep(i,N) h11pos[i+1] = max(h11pos[i+1], h11pos[i]); vector<pair<int, int>> subtree(N, {0,0}); rep(i,N) subtree[i] = { h11pos[hld.subtree(i).first], h11pos[hld.subtree(i).second] }; vector<Modint> X(N); rep(i,N){ int x; cin >> x; X[i] = Modint::raw(x); } nachia::DualSegtree<Affine, f1> rq(N, Affine::Construct(1,0)); nachia::DualSegtree<Affine, f1> rqh(N, Affine::Construct(1,0)); auto applyVtx = [&](int v, Affine f){ if(isOnHeavy(v)){ rqh.apply(hld.toSeq(v), f); } else{ rq.apply(pos[v], f); } }; auto heavyDec = [&](int v, int k) -> int { int s = hld.toSeq(v); s += k; if(s >= N) return -1; int w = hld.toVtx(s); if(!isOnHeavy(w)) return -1; return w; }; auto applyDec = [&](int v, int k, Affine f, bool doHeavy = true){ if(k == 0){ if(isOnHeavy(v)){ if(doHeavy) rqh.apply(hld.toSeq(v), f); } else{ rq.apply(pos[v], f); } return; } if(doHeavy){ int hd = heavyDec(v, k); if(hd >= 0) applyVtx(hd, f); } auto [l,r] = seq[v][k]; if(l <= r) rq.apply(l, r, f); }; auto applyPath = [&](int r, int c, Affine f){ for(auto [a, b] : hld.path(r, c)){ while(a < b && !isOnHeavy(hld.toVtx(a))){ int av = hld.toVtx(a); applyVtx(av, f); a++; } rqh.apply(a, b, f); } }; rep(i,Q){ int t; cin >> t; if(t == 1){ int v; cin >> v; v--; Affine f = (isOnHeavy(v) ? rqh.get(hld.toSeq(v)) : rq.get(pos[v])); cout << f.eval(X[v]).val() << '\n'; } if(t == 2){ int v, k, c, d; cin >> v >> k >> c >> d; v--; Affine af = Affine::Construct(c, d); while(k >= 0){ applyDec(v, k, af); k--; if(k < 0) break; applyDec(v, k, af); if(hld.parentOf(v) < 0){ while(k > 0){ k--; applyDec(v, k, af); } break; } v = hld.parentOf(v); } } if(t == 3){ int v, c, d; cin >> v >> c >> d; v--; Affine af = Affine::Construct(c, d); auto st = hld.subtree(v); rqh.apply(st.first, st.second, af); for(int k=0; k<=maxK; k++) applyDec(v, k, af, false); rq.apply(subtree[v].first, subtree[v].second, af); } if(t == 4){ int u, v, c, d; cin >> u >> v >> c >> d; u--; v--; Affine af = Affine::Construct(c, d); int h = hld.lca(u, v); applyPath(h, u, af); if(h != v) applyPath(hld.la(h, v, 1), v, af); } } return 0; }