結果
問題 | No.2340 Triple Tree Query (Easy) |
ユーザー | 沙耶花 |
提出日時 | 2023-06-02 23:07:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 411 ms / 5,000 ms |
コード長 | 1,817 bytes |
コンパイル時間 | 5,799 ms |
コンパイル使用メモリ | 270,680 KB |
実行使用メモリ | 20,044 KB |
最終ジャッジ日時 | 2023-08-28 05:37:45 |
合計ジャッジ時間 | 19,897 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 9 ms
4,380 KB |
testcase_02 | AC | 8 ms
4,380 KB |
testcase_03 | AC | 8 ms
4,380 KB |
testcase_04 | AC | 8 ms
4,376 KB |
testcase_05 | AC | 9 ms
4,380 KB |
testcase_06 | AC | 344 ms
13,856 KB |
testcase_07 | AC | 342 ms
13,864 KB |
testcase_08 | AC | 344 ms
13,888 KB |
testcase_09 | AC | 349 ms
13,808 KB |
testcase_10 | AC | 343 ms
13,816 KB |
testcase_11 | AC | 346 ms
14,016 KB |
testcase_12 | AC | 346 ms
14,008 KB |
testcase_13 | AC | 345 ms
14,024 KB |
testcase_14 | AC | 345 ms
13,968 KB |
testcase_15 | AC | 344 ms
13,872 KB |
testcase_16 | AC | 411 ms
20,044 KB |
testcase_17 | AC | 377 ms
17,944 KB |
testcase_18 | AC | 377 ms
17,652 KB |
testcase_19 | AC | 375 ms
19,276 KB |
testcase_20 | AC | 374 ms
17,468 KB |
testcase_21 | AC | 316 ms
14,192 KB |
testcase_22 | AC | 314 ms
14,240 KB |
testcase_23 | AC | 316 ms
14,300 KB |
testcase_24 | AC | 368 ms
14,124 KB |
testcase_25 | AC | 373 ms
13,944 KB |
testcase_26 | AC | 373 ms
13,972 KB |
testcase_27 | AC | 380 ms
13,988 KB |
testcase_28 | AC | 375 ms
14,036 KB |
testcase_29 | AC | 317 ms
14,288 KB |
testcase_30 | AC | 312 ms
14,132 KB |
testcase_31 | AC | 312 ms
14,140 KB |
testcase_32 | AC | 346 ms
14,020 KB |
testcase_33 | AC | 347 ms
14,040 KB |
testcase_34 | AC | 352 ms
14,044 KB |
testcase_35 | AC | 349 ms
14,032 KB |
testcase_36 | AC | 350 ms
13,984 KB |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 using P = pair<mint,mint> ; mint op(mint a,mint b){ return a+b; } mint e(){ return 0; } mint mapping(P a,mint b){ return a.first * b + a.second; } P composition(P a,P b){ return make_pair(b.first * a.first, b.second * a.first + a.second); } P id(){ return make_pair(1,0); } vector<int> ps; vector<int> l0,r0,l1,r1; vector<vector<int>> E; vector<int> is; vector<int> pos; void dfs(int cv,int pv){ ps[cv] = pv; l0[cv] = is.size(); l1[cv] = is.size(); rep(i,E[cv].size()){ int to = E[cv][i]; if(to==pv)continue; pos[to] = is.size(); is.push_back(to); } r0[cv] = is.size(); rep(i,E[cv].size()){ int to = E[cv][i]; if(to==pv)continue; dfs(to,cv); } r1[cv] = is.size(); } int main(){ int n,q; cin>>n>>q; E.resize(n); rep(i,n-1){ int a,b; cin>>a>>b; a--,b--; E[a].push_back(b); E[b].push_back(a); } l0.resize(n); l1.resize(n); r0.resize(n); r1.resize(n); ps.resize(n); is.push_back(0); pos.resize(n); pos[0] = 0; dfs(0,-1); vector<mint> x(n); rep(i,n){ int a; cin>>a; x[pos[i]] = a; } lazy_segtree<mint,op,e,P,mapping,composition,id> seg(x); rep(_,q){ int t; cin>>t; if(t==1){ int x; cin>>x; x--; cout<<seg.get(pos[x]).val()<<endl; } if(t==2){ int v,k,c,d; cin>>v>>k>>c>>d; v--; seg.apply(l0[v],r0[v],make_pair(c,d)); seg.apply(pos[v],make_pair(c,d)); if(v!=0)seg.apply(pos[ps[v]],make_pair(c,d)); } if(t==3){ int v,c,d; cin>>v>>c>>d; v--; seg.apply(l1[v],r1[v],make_pair(c,d)); seg.apply(pos[v],make_pair(c,d)); } } return 0; }