QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #409709 | #6742. Leaves | lzx2017# | WA | 2ms | 18064kb | C++20 | 2.2kb | 2024-05-12 16:21:09 | 2024-05-12 16:21:10 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll i,j,n,m,k,l,x,y,cnt,op,tree[20001][3],a[300001],f[1001][1001],siz[300001],in[300001],aim,qz[300001],dep[300001],len,tepan,g[300001];
int pd(ll x,ll y,ll z)
{
for(int i=1;i<=z;i++)
if(f[x][i]<f[y][i]) return 1;
else if(f[x][i]>f[y][i]) return 0;
tepan++;
return 1;
}
void dfs(ll x,ll y,ll father)
{
dep[x]=dep[father]+1;
if(tree[x][0]==-1&&tree[x][1]==-1)
{
f[x][1]=a[x];
siz[x]=1;
g[x]=0;
return;
}
dfs(tree[x][0],y,x);
dfs(tree[x][1],y-1,x);
if(y<=0)
{
ll gs=qz[len-dep[x]-1];
for(int i=1;i<=gs;i++)
f[x][i]=f[tree[x][0]][i];
for(int i=1;i<=gs;i++)
f[x][i+gs]=f[tree[x][1]][i];
g[x]=0;
}
else
{
ll gs=qz[len-dep[x]-1];
if(pd(tree[x][0],tree[x][1],gs)==1)
{
dfs(tree[x][1],y-g[tree[x][0]],x);
for(int i=1;i<=gs;i++)
f[x][i]=f[tree[x][0]][i];
for(int i=1;i<=gs;i++)
f[x][i+gs]=f[tree[x][1]][i];
g[x]=g[tree[x][0]]+g[tree[x][1]];
}
else
{
dfs(tree[x][0],y-g[tree[x][1]]-1,x);
for(int i=1;i<=gs;i++)
f[x][i]=f[tree[x][1]][i];
for(int i=1;i<=gs;i++)
f[x][i+gs]=f[tree[x][0]][i];
g[x]=g[tree[x][0]]+g[tree[x][1]]+1;
}
}
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%lld%lld",&n,&m);
qz[0]=1;
for(i=1;i<=60;i++) qz[i]=qz[i-1]*2;
for(i=1;i<=n;i++)
{
scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld",&x,&y);
tree[i][0]=x;
tree[i][1]=y;
in[x]++;in[y]++;
}
else
{
scanf("%lld",&x);
tree[i][0]=tree[i][1]=-1;
a[i]=x;
}
}
for(i=1;i<=n;i++)
if(in[i]==0)
{
aim=i;
break;
}
for(i=1;i<=60;i++)
if(qz[i]-1==n)
{
len=i;
break;
}
dfs(aim,m,0);
if(g[aim]<m)
{
int kk=m-g[aim];
if(m%2==0){
for(i=1;i<=qz[len-1];i++)
printf("%d ",f[aim][i]);
}
else
{
if(tepan!=0)
{
for(i=1;i<=qz[len-1];i++)
printf("%d ",f[aim][i]);
}
else
{
for(i=1;i<=qz[len-1]-2;i++)
printf("%d ",f[aim][i]);
printf("%d %d",f[aim][qz[len-1]],f[aim][qz[len-1]-1]);
}
}
}
else
{
for(i=1;i<=qz[len-1];i++)
printf("%d ",f[aim][i]);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 16032kb
input:
3 0 1 2 3 2 1 2 2
output:
1 2
result:
ok 2 number(s): "1 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 16112kb
input:
7 1 1 2 3 1 4 5 1 6 7 2 4 2 2 2 3 2 1
output:
2 4 3 1
result:
ok 4 number(s): "2 4 3 1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 16144kb
input:
7 2 1 2 3 1 4 5 1 6 7 2 4 2 2 2 3 2 1
output:
1 3 4 2
result:
ok 4 number(s): "1 3 4 2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 14096kb
input:
1 0 2 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #5:
score: 0
Accepted
time: 0ms
memory: 18064kb
input:
3 1 1 2 3 2 1 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 15980kb
input:
7 2 1 2 3 1 4 5 1 6 7 2 1 2 2 2 3 2 4
output:
1 2 3 4
result:
ok 4 number(s): "1 2 3 4"
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 16040kb
input:
999 480 1 3 2 1 4 5 1 6 7 1 9 8 1 10 11 1 13 12 1 14 15 1 16 17 1 19 18 1 21 20 1 23 22 1 25 24 1 27 26 1 28 29 1 30 31 1 33 32 1 35 34 1 37 36 1 38 39 1 41 40 1 42 43 1 45 44 1 46 47 1 48 49 1 51 50 1 52 53 1 55 54 1 56 57 1 58 59 1 61 60 1 62 63 1 64 65 1 67 66 1 69 68 1 71 70 1 73 72 1 74 75 1 76...
output:
result:
wrong answer Answer contains longer sequence [length = 500], but output contains 0 elements