QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274648 | #4941. Tree Beauty | anhduc2701 | WA | 92ms | 41196kb | C++23 | 2.6kb | 2023-12-03 19:39:06 | 2023-12-03 19:39:06 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int maxn=2e5+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;
}
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 i=1;i<=q;i++){
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;
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);
ans+=(r-l+1)*(y/d);
d*=k;
he++;
}
if(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<18;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);
he++;
}
ans+=B.get(tin[x],tout[x]);
cout << ans << '\n';
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 27728kb
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: 0ms
memory: 27672kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 92ms
memory: 41196kb
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 2805226296 2920352548 2920352548 7537734720 11295020015 7571909833 4383229800 19286079259 22947288874 15221147536 15428570536 14322314536 9135439455 12969783379 26980885791 25068338396 22398749036 27938581429 31534374661 745...
result:
wrong answer 8th lines differ - expected: '2782801948', found: '2805226296'