結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー vjudge1vjudge1
提出日時 2024-10-15 18:17:06
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,429 bytes
コンパイル時間 8,611 ms
コンパイル使用メモリ 282,428 KB
実行使用メモリ 34,944 KB
最終ジャッジ日時 2024-10-15 18:18:50
合計ジャッジ時間 90,616 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
13,056 KB
testcase_01 AC 8 ms
13,056 KB
testcase_02 AC 51 ms
13,440 KB
testcase_03 AC 55 ms
13,440 KB
testcase_04 AC 49 ms
13,312 KB
testcase_05 AC 54 ms
13,312 KB
testcase_06 AC 62 ms
13,440 KB
testcase_07 AC 6,484 ms
29,696 KB
testcase_08 AC 5,654 ms
29,696 KB
testcase_09 AC 7,183 ms
29,952 KB
testcase_10 AC 5,910 ms
29,952 KB
testcase_11 AC 6,860 ms
29,824 KB
testcase_12 AC 6,083 ms
29,824 KB
testcase_13 AC 6,348 ms
29,824 KB
testcase_14 AC 6,356 ms
29,696 KB
testcase_15 AC 6,565 ms
29,696 KB
testcase_16 AC 6,886 ms
29,696 KB
testcase_17 AC 441 ms
33,152 KB
testcase_18 AC 433 ms
34,688 KB
testcase_19 AC 429 ms
33,024 KB
testcase_20 AC 441 ms
34,048 KB
testcase_21 AC 436 ms
34,944 KB
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   25 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
main.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
main.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
main.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   48 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
main.cpp:62:24: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   62 | void dfs1(int x, int fa){
      |                        ^
main.cpp:62:24: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
main.cpp:62:24: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
main.cpp:62:24: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
main.cpp:76:24: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   76 | void dfs2(int x, int fa){
      |                        ^
main.cpp:76:24: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
main.cpp:76:24: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
main.cpp:76:24: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
main.cpp:90:29: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   90 | void js(int id, int l, int r){
      |                             ^
main.cpp:90:29: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
main.cpp:90:29: warning: bad option '-fcse-sk

ソースコード

diff # 

#include<bits/stdc++.h>
#define QWQ
#define int long long
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)


using namespace std;
const int MAXN = 1e5 + 5, Mod = 998244353;
int sub, n, t, a[MAXN], sd[MAXN], top[MAXN], fa[MAXN], sz[MAXN], son[MAXN];
int dfn[MAXN], id[MAXN], cnt;
struct Node{
  int sum, lzk = 1, lzb;
}tr[4 * MAXN];
vector<int> g[MAXN];
void dfs1(int x, int fa){
  ::fa[x] = fa;
  sz[x] = 1;
  sd[x] = sd[fa] + 1;
  for (auto v : g[x]){
    if (v != fa){
      dfs1(v, x);
      if (sz[v] > sz[son[x]]){
        son[x] = v;
      }
      sz[x] += sz[v];
    }
  }
}
void dfs2(int x, int fa){
  top[x] = fa;
  dfn[x] = ++cnt;
  id[cnt] = x;
  if (son[x]){
    dfs2(son[x], fa);
  }
  for (auto v : g[x]){
    if (v != ::fa[x] && v != son[x]){
      dfs2(v, v);
    }
  }
}
#define mid ((l + r) >> 1)
void js(int id, int l, int r){
  if (l == r){
    tr[id].sum = a[::id[l]];
    return ;
  }
  js(id * 2, l, mid);
  js(id * 2 + 1, mid + 1, r);
  // tr[id].sum = (tr[id * 2].sum + tr[id * 2 + 1].sum) % Mod;
}
void pushdown(int id, int l, int r){
  tr[id * 2].sum = ((tr[id * 2].sum * tr[id].lzk) % Mod + tr[id].lzb * (mid - l + 1) % Mod) % Mod;
  tr[id * 2].lzk = (tr[id * 2].lzk * tr[id].lzk) % Mod;
  tr[id * 2].lzb = (tr[id * 2].lzb * tr[id].lzk % Mod + tr[id].lzb) % Mod;
  tr[id * 2 + 1].sum = ((tr[id * 2 + 1].sum * tr[id].lzk) % Mod + tr[id].lzb * (r - mid) % Mod) % Mod;
  tr[id * 2 + 1].lzk = (tr[id * 2 + 1].lzk * tr[id].lzk) % Mod;
  tr[id * 2 + 1].lzb = (tr[id * 2 + 1].lzb * tr[id].lzk % Mod + tr[id].lzb) % Mod;
  tr[id].lzk = 1;
  tr[id].lzb = 0;
}
int find(int id, int l, int r, int ql, int qr){
  if (l > qr || r < ql){
    return 0;
  }else if (ql <= l && r <= qr){
    return tr[id].sum;
  }
  pushdown(id, l, r);
  return find(id * 2, l, mid, ql, qr) + find(id * 2 + 1, mid + 1, r, ql, qr);
}
void xg(int id, int l, int r, int ql, int qr, int k, int b){
  if (l > qr || r < ql){
    return ;
  }else if (ql <= l && r <= qr){
    tr[id].sum = (tr[id].sum * k % Mod + b * (r - l + 1) % Mod) % Mod;
    tr[id].lzb = (tr[id].lzb * k % Mod + b) % Mod;
    tr[id].lzk = (tr[id].lzk * k % Mod);
    return ;
  }
  pushdown(id, l, r);
  xg(id * 2, l, mid, ql, qr, k, b);
  xg(id * 2 + 1, mid + 1, r, ql, qr, k, b);
  // tr[id].sum = (tr[id * 2].sum + tr[id * 2 + 1].sum) % Mod;
}
void update(int x, int y, int k, int b){
  while (top[x] != top[y]){
    if (sd[top[x]] < sd[top[y]]){
      swap(x, y);
    }
    xg(1, 1, n, dfn[top[x]], dfn[x], k, b);
    x = fa[top[x]];
  }
  if (sd[x] > sd[y]){
    swap(x, y);
  }
  xg(1, 1, n, dfn[x], dfn[y], k, b);
}
void walk(int x, int r, int k, int b, int fa){
  if (r < 0){
    return ;
  }
  xg(1, 1, n, dfn[x], dfn[x], k, b);
  for (auto v : g[x]){
    if (v != fa){
      walk(v, r - 1, k, b, x);
    }
  }
}

namespace fastIO{
  char Buf[1 << 23], *P1 = Buf, *P2 = Buf;
  #define getchar() (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, 1 << 23, stdin), P1 == P2) ? EOF : *P1++)
  template<typename type>
  inline void read(type &x){
    x=0;
    bool f = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
      f |= ch == '-', ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
      x = x * 10 + (ch ^ 48), ch = getchar();
    }
    if(f){
      x = -x;
    }
  }
  template<typename type,typename... args>
  inline void read(type &x,args&... y){
    read(x), read(y...);
  }
  template<typename type>
  inline void print(type x, char s = ' ') {
    static int sta[130];
    int top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + '0'); 
    putchar(s);
  }
  template<typename type,typename... args>
  inline void print(type &x, args &... y, char s = ' '){
    print(x, s), print(y..., s);
  }
}
using namespace fastIO;
signed main(){
  #ifndef QWQ
  freopen("tour.in", "r", stdin);
  freopen("tour.out", "w", stdout);
  #endif
  read(n, t);
  for (int i = 1, u, v; i < n; i++){
    read(u, v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++){
    read(a[i]);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  js(1, 1, n);
  while (t--){
    int op;
    read(op);
    if (op == 1){
      int x;
      read(x);
      print(find(1, 1, n, dfn[x], dfn[x]), '\n');
    }else if (op == 4){
      int x, y, k, b;
      read(x, y, k, b);
      update(x, y, k, b);
    }else if (op == 3){
      int x, k, b;
      read(x, k, b);
      xg(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, k, b);
    }else {
      int x, r, k, b;
      read(x, r, k, b);
      walk(x, r, k, b, 0);
    }
  }
  return 0;
}
0