結果
| 問題 | No.2342 Triple Tree Query (Hard) |
| ユーザー |
 vjudge1
|
| 提出日時 | 2024-10-15 13:13:28 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,074 bytes |
| コンパイル時間 | 4,810 ms |
| コンパイル使用メモリ | 296,064 KB |
| 実行使用メモリ | 816,452 KB |
| 最終ジャッジ日時 | 2024-10-15 13:13:39 |
| 合計ジャッジ時間 | 9,652 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| 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 | -- | - |
ソースコード
#pragma GCC optimize(3,"Ofast","no-stack-protector","fast-math")
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[r] + 1
using namespace std;
void file() {
freopen("tour.in", "r", stdin);
freopen("tour.out", "w", stdout);
}
using ll = long long;
template <typename T> using vec = vector<T> ;
const int mod = 998244353;
void Add(int& x, int y) { ((x += y) >= mod) && (x -= mod); }
void Sub(int& x, int y) { ((x -= y) < 0) && (x += mod); }
int Sum(int x, int y) { return Add(x, y), x; }
int Dif(int x, int y) { return Sub(x, y), x; }
int qpow(int x, int y) {
int b = x, r = 1;
for(; y; b = (ll)b * b % mod, y /= 2)
if(y & 1) r = (ll)r * b % mod;
return r;
}
const int kL = 1e5 + 5, inf = 1e9;
int sub, n, q, dtot;
array<vec<int>, kL> g;
array<int, kL> a, dep, dfn, siz, son, top, fa, drev;
namespace Init {
void dfs(int x, int Fa) {
siz[x] = 1;
dep[x] = dep[fa[x] = Fa] + 1;
for(int to : g[x]) {
if(to == Fa) continue;
dfs(to, x);
siz[x] += siz[to];
if(siz[son[x]] < siz[to])
son[x] = to;
}
}
void dfs2(int x, int tp) {
top[x] = tp;
drev[dfn[x] = ++dtot] = x;
if(son[x]) dfs2(son[x], tp);
for(int to : g[x])
if((to ^ fa[x]) && (to ^ son[x]))
dfs2(to, to);
}
}
struct info {
int k, b;
info() { k = 1; b = 0; }
info(int _k, int _b) { k = _k; b = _b; }
int operator () (int x) { return ((ll)k * x + b) % mod; }
};
info& operator *= (info& x, const info& y) {
x.k = (ll)x.k * y.k % mod;
x.b = ((ll)y.k * x.b + y.b) % mod;
return x;
}
info operator * (info x, info y) { return x *= y, x; }
info Inv(const info& x) {
int inv = qpow(x.k, mod - 2);
return info(inv, (ll)(mod - x.b) * inv % mod);
}
namespace Task1 {
int btot, bsc, dsc;
array<int, kL> bfn, brev;
array<info, kL> val;
pair<int, int> seg[kL][13];
array<int, 501> bl, br, dl, dr;
void bfs(int s) {
queue<int> q; q.push(s);
while(q.size()) {
int x = q.front(); q.pop();
brev[bfn[x] = ++btot] = x;
for(int to : g[x])
if(!bfn[to]) q.push(to);
}
}
void updated(int l, int r, const info& v) {
for(int i = l; i <= r; i++) val[drev[i]] *= v;
}
void updateb(int l, int r, const info& v) {
for(int i = l; i <= r; i++) val[brev[i]] *= v;
}
void getd(int x, int y) {
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
dsc++;
dl[dsc] = dfn[top[x]];
dr[dsc] = dfn[x];
x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y);
dsc++;
dl[dsc] = dfn[x];
dr[dsc] = dfn[y];
}
void getb(int x, int d) {
int last = 0;
for(int p = x, i = 0; i <= d; p = fa[last = p], i++) {
bsc++;
bl[bsc] = br[bsc] = bfn[p];
for(int j = 1; i + j <= d; j++) {
int tl, tr, l, r;
tie(l, r) = seg[p][j];
tie(tl, tr) = seg[last][j - 1];
if(l > r) break;
if(tl > tr) {
bsc++;
bl[bsc] = l; br[bsc] = r;
}else {
if(l < tl) {
bsc++;
bl[bsc] = l; br[bsc] = tl - 1;
}
if(r > tr) {
bsc++;
bl[bsc] = tr + 1; br[bsc] = r;
}
}
}
}
}
void solve() {
bfs(1);
for(auto& k : seg)
for(auto& t : k) t = pair<int, int> {inf, 0};
for(int i = 1; i <= n; i++)
seg[i][0] = pair<int, int> {bfn[i], bfn[i]};
for(int i = 1; i < 12; i++)
for(int j = 1; j <= n; j++) {
int l = inf, r = 0;
for(int to : g[j])
if(bfn[to] > bfn[j]) {
l = min(l, seg[to][i - 1].first);
r = max(r, seg[to][i - 1].second);
}
seg[j][i] = pair<int, int> {l, r};
}
for(int op, x, y, k, b; q--; ) {
cin >> op;
if(op == 1) {
cin >> x;
cout << val[x](a[x]) << "\n";
}else if(op == 2) {
cin >> x >> y >> k >> b;
const info val (k, b);
dsc = 0;
getd(x, y);
for(int i = 1; i <= dsc; i++)
updated(dl[i], dr[i], val);
}else if(op == 3) {
cin >> x >> k >> b;
const info val (k, b);
updated(dfn[x], dfn[x] + siz[x] - 1, val);
}else {
cin >> x >> y >> k >> b;
const info val (k, b);
bsc = 0; getb(x, y);
for(int i = 1; i <= bsc; i++)
updateb(bl[i], br[i], val);
}
}
}
}
namespace Task2 {
array<array<info, 13>, kL> tag, invtag;
void subtree(int x, int y, const info& val, const info& invval) {
for(int i = 0; i <= y; i++) {
info sum, inv;
for(int p = fa[x], j = i + 1; p && (j <= 10); p = fa[p], j++) {
sum = sum * tag[p][j];
inv = invtag[p][j] * inv;
}
tag[x][i] = tag[x][i] * sum * val * inv;
invtag[x][i] = sum * invval * inv * invtag[x][i];
}
}
void update(int x, int y, int k, int b) {
const info val (k, b), inv = Inv(val);
info tmp = val * inv;
for(int last = 0, p = x, i = y; p && ~i; p = fa[last = p], i--) {
if(last && i)
subtree(last, i - 1, inv, val);
subtree(p, i, val, inv);
}
}
ll query(int x) {
info cur = tag[x][0];
for(int p = fa[x], i = 1; p && (i <= 10); p = fa[p], i++)
cur *= tag[p][i];
return cur (a[x]);
}
void solve() {
for(int op, x, y, k, b; q--; ) {
cin >> op >> x;
if(op == 1) cout << query(x) << "\n";
else {
cin >> y >> k >> b;
update(x, y, k, b);
}
}
}
}
namespace Task3 {
const int sL = 4e5 + 5;
#define ls (o << 1)
#define rs (o << 1 | 1)
struct SGT {
array<info, sL> s, t;
void pu(int o) { s[o] = s[ls] * s[rs]; }
void ad(int o, const info& v) { s[o] *= v; t[o] *= v; }
void pd(int o) {
if((t[o].k ^ 1) || (t[o].b)) {
ad(ls, t[o]); ad(rs, t[o]); t[o] = info();
}
}
void update(int o, int l, int r, int x, int y, const info& v) {
if((l > y) || (r < x)) return ;
if((l >= x) && (r <= y)) return ad(o, v);
pd(o); int mid = (l + r) >> 1;
update(ls, l, mid, x, y, v);
update(rs, mid + 1, r, x, y, v);
pu(o);
}
info query(int o, int l, int r, int x) {
if(l == r) return s[o];
pd(o); int mid = (l + r) >> 1;
if(mid < x) return query(rs, mid + 1, r, x);
return query(ls, l, mid, x);
}
}sgt;
int query(int x) {
return sgt.query(1, 1, n, dfn[x])(a[x]);
}
void update(int x, int y, int k, int b) {
const info val (k, b);
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
sgt.update(1, 1, n, dfn[top[x]], dfn[x], val);
x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y);
sgt.update(1, 1, n, dfn[x], dfn[y], val);
}
void tree(int x, int k, int b) {
const info val (k, b);
sgt.update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, val);
}
void solve() {
for(int op, x, y, k, b; q--; ) {
cin >> op >> x;
if(op == 1) cout << query(x) << "\n";
else if(op == 2) {
cin >> y >> k >> b;
update(x, y, k, b);
}else { cin >> k >> b; tree(x, k, b); }
}
}
}
namespace Task4 {
void solve() {
for(int op, x, y, k, b; q--; ) {
cin >> op >> x;
if(op == 1)
cout << ((Task2::query(x) + Task3::query(x) - a[x]) % mod + mod) % mod << "\n";
else if(op == 2) {
cin >> y >> k >> b;
Task3::update(x, y, k, b);
}else if(op == 3) {
cin >> k >> b;
Task3::tree(x, k, b);
}else {
cin >> y >> k >> b;
Task2::update(x, y, k, b);
}
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> sub >> n >> q;
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++) cin >> a[i];
Init::dfs(1, 0); Init::dfs2(1, 1);
if((sub == 1) || (sub == 2) || (sub == 3) || (sub == 5) || (sub == 7) || (sub == 8))
return Task1::solve(), 0;
if(sub == 4) return Task3::solve(), 0;
if(sub == 6) return Task4::solve(), 0;
return 0;
}