QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#647279 | #4941. Tree Beauty | Vermeil | WA | 252ms | 46548kb | C++17 | 4.3kb | 2024-10-17 13:10:38 | 2024-10-17 13:10:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
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 dp[101010][19];
ll updPar[101010][19];
ll P[101010];
int L[101010], R[101010];
int B[101010], revB[101010];
int idx = 0;
void dfs(int x){
L[x] = ++idx;
for (int i: g[x]){
par[i] = x;
dfs(i);
for (int j=0;j<18;j++){
dp[x][j + 1] += dp[i][j];
}
}
dp[x][0] = 1;
R[x] = idx;
}
void bfs(){
queue<int> que;
que.push(1);
int bfn = 0;
while(!que.empty()){
int x = que.front();
que.pop();
B[x] = ++bfn;
revB[bfn] = x;
for (int i: g[x]){
que.push(i);
}
}
}
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);
bfs();
SegTree s1(n), s2(n), s3(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;
for (int i=0;i<19;i++){
updPar[x][i] += val;
sum += val * dp[x][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]);
// cout<<"s1+s2 : "<<ans<<endl;
int cur = par[x];
vector<ll> intervals = {1};
int l = B[x], r = B[x];
for (int i=1;i<19;i++){
int nl = 0, nr = 0;
int lo, hi;
lo = 1, hi = n;
while (lo <= hi){
int mid = (lo + hi) / 2;
int ver = B[par[revB[mid]]];
if (ver < l) lo = mid + 1;
else hi = mid - 1;
}
nl = lo;
lo = 1, hi = n;
while (lo <= hi){
int mid = (lo + hi) / 2;
int ver = B[par[revB[mid]]];
if (ver <= r) lo = mid + 1;
else hi = mid - 1;
}
nr = hi;
if (nr < nl){
while (intervals.size() < 19){
intervals.push_back(0);
}
break;
}
intervals.push_back(nr - nl + 1);
l = nl;
r = nr;
}
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: 3ms
memory: 12128kb
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: 11072kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 252ms
memory: 46548kb
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'