QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#274732 | #4941. Tree Beauty | anhduc2701 | WA | 96ms | 90108kb | C++23 | 2.9kb | 2023-12-03 20:48:20 | 2023-12-03 20:48:21 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define int long long
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int n,q;
vector<int>G[maxn];
int p[maxn];
struct segtree{
int N;
vector<ll>st;
vector<ll>lazy;
void init(int _n){
N=_n;
st.assign(4*N+5,0);
lazy.assign(4*N+5,0);
}
void push(int id,int l,int mid,int r){
if(lazy[id]){
st[id*2]+=lazy[id]*(mid-l+1);
st[id*2+1]+=lazy[id]*(r-mid);
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,ll val){
if(r<u || v<l)return;
if(u<=l && r<=v){
st[id]+=val*(r-l+1);
lazy[id]+=val;
return;
}
int mid=(l+r)/2;
push(id,l,mid,r);
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
st[id]=st[id*2]+st[id*2+1];
}
ll get(int id,int l,int r,int u,int v){
if(r<u || v<l)return 0;
if(u<=l && r<=v){
return st[id];
}
int mid=(l+r)/2;
push(id,l,mid,r);
return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
void upd(int l,int r,ll val){
if(l<=r){
update(1,1,N,l,r,val);
}
}
ll get(int l,int r){
if(l>r)return 0;
return get(1,1,N,l,r);
}
}A[maxn],B;
int tin[maxn];
int eu[maxn];
int tout[maxn];
int h[maxn];
int ma=0;
int s=0;
vector<int>D[maxn];
void dfs(int u){
tin[u]=++s;
eu[s]=u;
ma=max(ma,h[u]);
D[h[u]].pb(tin[u]);
for(auto v:G[u]){
h[v]=h[u]+1;
dfs(v);
}
tout[u]=s;
}
ll value[maxn];
signed main(){
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
cin.tie(0),cout.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for(int i=2;i<=n;i++){
cin >> p[i];
G[p[i]].pb(i);
}
dfs(1);
for(int i=0;i<=ma;i++){
A[i].init(D[i].size());
}
B.init(n);
for(int ti=1;ti<=q;ti++){
int type;
cin >> type;
if(type==1){
int x,y,k;
cin >> x >> y >> k;
if(k==1){
B.upd(tin[x],tout[x],y);
}
else{
int d=1;
int he=h[x];
ll ans=0;
vector<ll>con;
while(y/d>0){
int l=lower_bound(D[he].begin(),D[he].end(),tin[x])-D[he].begin()+1;
int r=upper_bound(D[he].begin(),D[he].end(),tout[x])-D[he].begin();
A[he].upd(l,r,y/d);
con.pb((r-l+1)*(y/d));
d*=k;
he++;
}
for(int i=1;i<=17-(int)con.size();i++){
x=p[x];
}
while(p[x]!=0 && con.size()){
ans+=con.back();
con.pop_back();
x=p[x];
value[x]+=ans;
}
if(p[x]!=1){
B.upd(tin[p[x]],tin[p[x]],ans);
}
}
}
else{
int x;
cin >> x;
int he=h[x];
ll ans=0;
for(int i=0;i<17;i++){
int l=lower_bound(D[he].begin(),D[he].end(),tin[x])-D[he].begin()+1;
int r=upper_bound(D[he].begin(),D[he].end(),tout[x])-D[he].begin();
ans+=A[he].get(l,r);
// cout << he << ' ' << l << ' ' <<r << ' ' << A[he].get(l,r) << '\n';
he++;
}
ans+=B.get(tin[x],tout[x]);
cout << ans+value[x] << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 67036kb
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: 12ms
memory: 66752kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 96ms
memory: 90108kb
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 2920352548 1987509504 2920352548 2782801948 2920352548 2920352548 7518672977 11295020015 7543062544 4383229800 19258702398 22947288874 15221147536 15428570536 14322314536 9119623396 12969783379 26872020588 25039643385 22398749036 27923029652 31534374661 745...
result:
wrong answer 2462nd lines differ - expected: '4764338999495', found: '4764272514590'