QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#647334 | #4941. Tree Beauty | Vermeil | WA | 115ms | 27240kb | C++17 | 3.2kb | 2024-10-17 13:25:11 | 2024-10-17 13:25:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SegTree{
vector<ll> seg, lazy;
int sz;
SegTree(int n){
sz = n;
seg.resize(sz * 4, 0);
lazy.resize(sz * 4, 0);
}
void prop(int x, int s, int e){
if (!lazy[x]) return;
seg[x] += lazy[x] * (e - s + 1);
if (s ^ e){
for (int i:{x*2,x*2+1}){
lazy[i]+=lazy[x];
}
}
lazy[x] = 0;
}
void upd(int x, int s, int e, int l, int r, ll v){
if (e < l || r < s) return;
prop(x, s, e);
if (l <= s && e <= r){
lazy[x] = v;
prop(x, s, e);
return;
}
int m = (s + e) / 2;
upd(x * 2, s, m, l, r, v);
upd(x * 2 + 1, m + 1, e, l, r, v);
seg[x] = seg[x * 2] + seg[x * 2 + 1];
}
ll qry(int x, int s, int e, int l, int r){
if (e < l || r < s) return 0;
prop(x, s, e);
if (l <= s && e <= r) return seg[x];
int m = (s + e) / 2;
return qry(x * 2, s, m, l, r) + qry(x * 2 + 1, m + 1, e, l, r);
}
void upd(int l, int r, ll v){
upd(1, 1, sz, l, r, v);
}
ll qry(int l, int r){
return qry(1, 1, sz, l, r);
}
};
int n, q;
vector<int> g[101010];
int par[101010];
ll updPar[101010][19];
vector<int> vetx[101010];
int L[101010], R[101010], dep[101010];
int idx = 0;
void dfs(int x){
L[x] = ++idx;
vetx[dep[x]].push_back(L[x]);
for (int i: g[x]){
par[i] = x;
dep[i] = dep[x] + 1;
dfs(i);
}
R[x] = idx;
}
vector<ll> getIntervals(int x){
vector<ll> ret;
for (int i=0;i<19;i++){
int d = dep[x] + i;
auto rr = upper_bound(vetx[d].begin(), vetx[d].end(), R[x]);
auto ll = lower_bound(vetx[d].begin(), vetx[d].end(), L[x]);
ret.push_back((int)(rr - ll));
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>q;
for (int i=2;i<=n;i++){
int x;cin>>x;
g[x].push_back(i);
}
dfs(1);
SegTree s1(n), s2(n);
while (q--){
ll op, y, k;
int x;
cin>>op;
if (op==1){
cin>>x>>y>>k;
if (k > 1){
ll sum = 0;
ll val = y;
vector<ll> intervals = getIntervals(x);
for (int i=0;i<19;i++){
updPar[x][i] += val;
sum += val * intervals[i];
val /= k;
}
s2.upd(L[x], L[x], sum);
}
else{
s1.upd(L[x], R[x], y);
}
}
else{
cin>>x;
ll ans = 0;
ans += s1.qry(L[x], R[x]);
ans += s2.qry(L[x], R[x]);
int cur = par[x];
vector<ll> intervals = getIntervals(x);
for (int d=1;cur&&d<19;d++,cur=par[cur]){
for (int i=0;i+d<19;i++){
ans += updPar[cur][i + d] * intervals[i];
}
}
cout<<ans<<'\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11504kb
input:
5 5 1 1 3 3 1 1 99 2 2 1 2 3 1 3 2 3 2 3
output:
245 97 99
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 11768kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 115ms
memory: 27240kb
input:
100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1818724600 1818724600 1818724600 672469600 2695839402 1987509504 2695839402 2707607620 2695839402 2695839402 6169484781 8462490815 6059721540 3956948412 16426173198 19999836240 12388618336 12596041336 11489785336 7327275384 10382901054 22395595829 20563218626 17544502851 21935873619 25432295194 7454...
result:
wrong answer 5th lines differ - expected: '2920352548', found: '2695839402'