QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686523 | #4941. Tree Beauty | SanguineChameleon# | WA | 59ms | 38096kb | C++20 | 2.8kb | 2024-10-29 14:01:47 | 2024-10-29 14:01:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define mp make_pair
#define eb emplace_back
#define pb push_back
typedef pair<int,int> pii;
struct node{
//range sum segtree
int s,e;
int v=0, lz=0;
node *l, *r;
node(int ss,int ee){
s=ss;e=ee;
if(s==e){
l=r=NULL;
}else{
l=new node(s,(s+e)/2);
r=new node((s+e)/2+1,e);
}
}
void propagate(){
if(lz==0)return;
if(s<e){
l->update(s,e,lz);
r->update(s,e,lz);
}
lz=0;
}
//propagate
void update(int a,int b,int c){
if(a<=s && e<=b){
lz+=c;
v+=(e-s+1)*c;
return;
}
propagate();
if(a<=(s+e)/2)l->update(a,b,c);
if((s+e)/2<b) r->update(a,b,c);
v = l->v + r->v;
}
int query(int a,int b){
if(a<=s && e<=b){
return v;
}
int ans=0;
if(a<=(s+e)/2)ans+=l->query(a,b);
if((s+e)/2<b) ans+=r->query(a,b);
return ans;
}
} *root;
const int lg = 18;
const int mxn = 1e5+5;
int par[mxn];
int pre[mxn],nex=1,las[mxn];
int delt[mxn][lg];//updates for subseq layers
int cntt[mxn][lg];//count of nodes in each layer
vector<int> adjl[mxn];
void dfs(int nd,int p=-1){
par[nd]=p;
pre[nd]=nex++;
cntt[nd][0]=1;
for(int x:adjl[nd]){
if(x==p)continue;
dfs(x,nd);
for(int i=1;i<lg;i++){
cntt[nd][i]+=cntt[x][i-1];
if(cntt[x][i-1]==0)break;
}
}
las[nd]=nex-1;
}
int32_t main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int n,q;
cin>>n>>q;
for(int i=2;i<=n;i++){
int a;
cin>>a;
adjl[a].pb(i);
}
dfs(1);
root=new node(1,n);
while(q--){
int t,x,y,k;
cin>>t;
if(t==1){
cin>>x>>y>>k; //update
if(k==1){
root->update(pre[x],las[x],y);
continue;
}
int summ=0;
for(int i=0;i<lg;i++){
if(k==0)break;
delt[x][i]+=y;
y/=k;
summ+=delt[x][i]*cntt[x][i];
}
root->update(pre[x],pre[x],summ);
}else{
//query
cin>>x;
int ans = root->query(pre[x],las[x]);
//loop thru prev 18
int u=x;
for(int i=1;i<lg;i++){
u=par[u];
if(u==-1)break;
for(int j=0;j+i<lg;j++){
ans+=cntt[x][j] * delt[u][j+i];
}
}
cout<<ans<<'\n';
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7660kb
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: 7720kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 59ms
memory: 38096kb
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 0 2920352548 1613238404 2920352548 2743370776 2920352548 2920352548 6948772227 10957009915 5694550860 2884687788 17107200878 22493981008 8571429786 8571429786 8571429786 6709718368 9573949604 26872020588 24947756711 21992660896 27097673484 31423167461 0 23149628436 2...
result:
wrong answer 4th lines differ - expected: '672469600', found: '0'