結果
問題 | No.2340 Triple Tree Query (Easy) |
ユーザー | 沙耶花 |
提出日時 | 2023-06-02 23:07:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 420 ms / 5,000 ms |
コード長 | 1,817 bytes |
コンパイル時間 | 4,760 ms |
コンパイル使用メモリ | 274,216 KB |
実行使用メモリ | 21,848 KB |
最終ジャッジ日時 | 2024-06-09 01:09:37 |
合計ジャッジ時間 | 19,721 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 10 ms
5,248 KB |
testcase_02 | AC | 10 ms
5,376 KB |
testcase_03 | AC | 10 ms
5,376 KB |
testcase_04 | AC | 10 ms
5,376 KB |
testcase_05 | AC | 11 ms
5,376 KB |
testcase_06 | AC | 381 ms
14,180 KB |
testcase_07 | AC | 385 ms
14,160 KB |
testcase_08 | AC | 382 ms
14,284 KB |
testcase_09 | AC | 392 ms
14,284 KB |
testcase_10 | AC | 376 ms
14,284 KB |
testcase_11 | AC | 380 ms
14,156 KB |
testcase_12 | AC | 375 ms
14,280 KB |
testcase_13 | AC | 383 ms
14,280 KB |
testcase_14 | AC | 381 ms
14,156 KB |
testcase_15 | AC | 372 ms
14,280 KB |
testcase_16 | AC | 419 ms
21,848 KB |
testcase_17 | AC | 413 ms
19,208 KB |
testcase_18 | AC | 407 ms
18,916 KB |
testcase_19 | AC | 420 ms
21,132 KB |
testcase_20 | AC | 412 ms
18,756 KB |
testcase_21 | AC | 326 ms
14,432 KB |
testcase_22 | AC | 337 ms
14,444 KB |
testcase_23 | AC | 338 ms
14,436 KB |
testcase_24 | AC | 410 ms
14,332 KB |
testcase_25 | AC | 411 ms
14,176 KB |
testcase_26 | AC | 398 ms
14,204 KB |
testcase_27 | AC | 403 ms
14,212 KB |
testcase_28 | AC | 405 ms
14,336 KB |
testcase_29 | AC | 340 ms
14,432 KB |
testcase_30 | AC | 337 ms
14,436 KB |
testcase_31 | AC | 336 ms
14,432 KB |
testcase_32 | AC | 363 ms
14,452 KB |
testcase_33 | AC | 371 ms
14,332 KB |
testcase_34 | AC | 372 ms
14,456 KB |
testcase_35 | AC | 375 ms
14,336 KB |
testcase_36 | AC | 368 ms
14,328 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; }