QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401210 | #946. Magic Tree | sichengzhou# | 0 | 80ms | 21192kb | C++14 | 4.0kb | 2024-04-28 08:44:10 | 2024-04-28 08:44:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=22;
int n,m,K,fa[N],d[N],w[N];
struct Edge{
int v,nxt;
}e[N];
int h[N],tot1;
void addEdge(int u,int v)
{
tot1++;
e[tot1].v=v;e[tot1].nxt=h[u];
h[u]=tot1;
}
struct Seg{
int l,r;
LL val,mx,lz;
}t[N<<2];
vector<pair<int,LL> >f[N];
void update(int p)
{
t[p].val=max(t[t[p].l].val,t[t[p].r].val);
}
void pushlz(int p,LL z)
{
t[p].val+=z;
if(t[p].mx==0)
{
t[p].lz+=z;
}else{
t[p].mx+=z;
}
}
void pushmx(int p,LL z)
{
t[p].val=z;
t[p].mx=z;
t[p].lz=0;
}
void lzdown(int p)
{
if(t[p].l)
{
pushlz(t[p].l,t[p].lz);
if(t[p].mx)pushmx(t[p].l,t[p].mx);
}
if(t[p].r)
{
pushlz(t[p].r,t[p].lz);
if(t[p].mx)pushmx(t[p].r,t[p].mx);
}
t[p].mx=0;t[p].lz=0;
}
LL val;
LL add(int p,int l,int r,int x,int y,LL z)
{
if(x<=l&&r<=y)
{
pushlz(p,z);
return t[p].val;
}
lzdown(p);
int mid=l+r>>1;
LL ret=0;
if(x<=mid)
{
ret=add(p<<1,l,mid,x,y,z);
}
if(mid+1<=y)
{
ret=add(p<<1|1,mid+1,r,x,y,z);
}
update(p);
return ret;
}
void change(int p,int l,int r,int x,int y,LL z)
{
if(x>y)return ;
if(x<=l&&r<=y)
{
if(l==r)
{
if(t[p].val<z)
{
pushmx(p,z);
}
return ;
}
lzdown(p);
int mid=l+r>>1;
if(t[p<<1].val<z)
{
pushmx(p<<1,z);
change(p<<1|1,mid+1,r,x,y,z);
}else{
change(p<<1,l,mid,x,y,z);
}
return ;
}
lzdown(p);
int mid=l+r>>1;
if(x<=mid)
{
change(p<<1,l,mid,x,y,z);
}
if(mid+1<=y)
{
change(p<<1|1,mid+1,r,x,y,z);
}
update(p);
}
LL query(int p,int l,int r,int x)
{
if(l==r)
{
return t[p].val;
}
lzdown(p);
int mid=l+r>>1;
if(x<=mid)
{
return query(p<<1,l,mid,x);
}else{
return query(p<<1|1,mid+1,r,x);
}
}
int sz[N],son[N],dfn[N],rnk[N],idx;
void dfs0(int u)
{
dfn[u]=++idx;rnk[idx]=u;
sz[u]=1;son[u]=0;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u])
{
continue;
}
fa[v]=u;
dfs0(v);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])
{
son[u]=v;
}
}
}
void dfs(int u)
{
// cout<<u<<"b\n";
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==son[u])
{
continue;
}
dfs(v);
}
if(son[u])
{
dfs(son[u]);
}
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==son[u])
{
continue;
}
LL pre=0;
for(int j=0;j<f[v].size();j++)
{
add(1,1,K,f[v][j].first,K,f[v][j].second-pre);
pre=f[v][j].second;
}
}
if(w[u])
{
LL val=add(1,1,K,d[u],d[u],w[u]);
change(1,1,K,d[u]+1,K,val);
}
if(son[fa[u]]!=u)
{
for(int i=dfn[u];i<=dfn[u]+sz[u]-1;i++)
{
int v=rnk[i];
if(w[v])
{
f[u].push_back(make_pair(d[v],0));
}
}
sort(f[u].begin(),f[u].end());
unique(f[u].begin(),f[u].end());
for(int i=0;i<f[u].size();i++)
{
f[u][i].second=query(1,1,K,f[u][i].first);
}
pushmx(1,0);
}
// cout<<u<<"e\n";
}
int main()
{
int x;
scanf("%d%d%d",&n,&m,&K);
for(int i=2;i<=n;i++)
{
scanf("%d",&fa[i]);
addEdge(fa[i],i);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
scanf("%d%d",&d[x],&w[x]);
}
dfs0(1);
dfs(1);
printf("%lld\n",f[1][f[1].size()-1].second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 8008kb
input:
10 9 10 1 1 2 2 3 1 3 8 3 5 4 1 9 4 1 6 8 1 3 1 1 4 9 1 10 1 1 2 6 1 8 7 1 7 9 1
output:
2
result:
wrong answer expected '7', found '2'
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 0
Wrong Answer
time: 80ms
memory: 21192kb
input:
100000 25000 100000 1 1 2 1 2 1 5 8 8 2 5 2 2 3 1 2 11 10 18 2 9 9 9 8 1 19 18 22 20 17 20 13 30 5 9 8 13 2 19 26 14 31 23 22 2 21 8 1 22 9 50 19 49 42 47 19 21 57 9 52 41 39 10 14 60 56 34 17 18 22 53 5 34 64 29 72 33 11 9 67 58 10 58 70 57 26 65 10 15 64 67 20 26 13 51 81 11 78 40 53 70 33 34 92 7...
output:
16356820834
result:
wrong answer expected '12471468294549', found '16356820834'
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 11
Accepted
time: 1ms
memory: 8096kb
input:
1000 500 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
3
result:
ok answer is '3'
Test #16:
score: -11
Wrong Answer
time: 1ms
memory: 8152kb
input:
1000 500 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
8
result:
wrong answer expected '38', found '8'
Subtask #4:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 43ms
memory: 20748kb
input:
100000 90000 2 1 1 3 2 1 2 1 5 1 8 11 9 1 8 12 7 1 2 7 6 12 9 16 18 13 10 23 27 26 17 23 10 24 11 21 13 30 1 11 6 13 8 30 15 17 34 39 41 32 29 27 17 21 12 26 33 10 50 29 17 46 33 21 28 47 26 3 67 38 5 10 45 61 70 59 17 46 40 20 58 67 68 15 62 71 71 57 32 81 18 66 7 14 51 67 92 86 38 88 60 45 54 5 59...
output:
-542508469584869850
result:
wrong answer expected '38521956905095', found '-542508469584869850'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Wrong Answer
Test #31:
score: 0
Wrong Answer
time: 3ms
memory: 11564kb
input:
20000 800 60000 1 1 1 2 3 1 7 8 6 1 7 6 1 7 14 16 11 13 14 3 11 11 4 2 5 24 20 24 16 30 15 3 24 31 12 7 2 29 14 25 39 23 16 33 32 33 34 9 13 37 33 23 15 21 28 39 51 19 6 50 54 55 8 40 3 7 34 19 28 15 61 18 22 28 38 15 47 37 42 73 38 61 10 7 30 58 41 43 69 89 62 84 30 68 92 84 43 59 44 75 8 100 83 18...
output:
-11454360730
result:
wrong answer expected '386917987664', found '-11454360730'
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%