QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #402592 | #6742. Leaves | mulberry | WA | 1ms | 3964kb | C++23 | 2.6kb | 2024-04-30 23:45:19 | 2024-04-30 23:45:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int rt;
int n, m;
int dep[2005];
int a[2005], fa[2005];
bool mark[2005];
int L[2005], R[2005];
void up(int u){
while(!mark[u]){
mark[u] = 1;
u = fa[u];
}
}
int find(int u){
if(!mark[u])return u;
int f = 0;
if(L[u])f = find(L[u]);
if(!f && R[u])f = find(R[u]);
return f;
}
struct node{
int id, num, sum;
}tmp[2005];
bool cmp(node a, node b){
if(a.num != b.num) return a.num < b.num;
return a.sum < b.sum;
}
int tot;
void collect(int u, int sum){
if(!L[u] && !R[u]){
++tot;
tmp[tot] = node{u, a[u], sum};
return;
}
if(L[u])collect(L[u], sum);
if(R[u])collect(R[u], sum + 1);
}
int num = 0;
int ans[20005];
void print(int u){
if(!L[u] && !R[u]){
ans[++num] = a[u];
// printf("%d ", a[u]);
return;
}
print(L[u]);
print(R[u]);
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
int f, u, v;
scanf("%d", &f);
if(f == 1){
scanf("%d%d", &u, &v);
L[i] = u;
R[i] = v;
fa[u] = i, fa[v] = i;
}else{
scanf("%d", &u);
a[i] = u;
}
}
for (int i = 1; i <= n; i++)
if(fa[i] == 0)rt = i;
// printf("rt = %d\n", rt);
// dfs(rt);
while(m){
int s = find(rt), x = 0;
if(!s)break;
tot = 0;
collect(s, 0);
// printf("s = %d tot = %d\n", s, tot);
sort(tmp + 1, tmp + tot + 1, cmp);
for (int i = 1; i <= tot ; i++){
// printf(" id = %d a = %d sum = %d\n", tmp[i].id, tmp[i].num, tmp[i].sum);
// cout << tmp[i].s << endl;
if(m >= tmp[i].sum){
m -= tmp[i].sum;
x = tmp[i].id;
int t = x;
while(t != s){
if(t == R[fa[t]]){
// printf(" swap = %d %d\n", L[fa[t]], R[fa[t]]);
swap(L[fa[t]], R[fa[t]]);
}
t = fa[t];
}
break;
}
}
if(!x)break;
up(x);
mark[x] = mark[R[fa[x]]] = 1;
}
print(rt);
if(m % 2 == 1)swap(ans[num - 1], ans[num]);
for(int i = 1; i <= num; i++)
printf("%d ", ans[i]);
}
/*
15 4
1 2 3
1 4 5
1 6 7
1 8 9
1 10 11
1 12 13
1 14 15
2 7
2 8
2 6
2 5
2 1
2 2
2 4
2 3
2 4
2 2
2 3
2 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
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: 3960kb
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: 0ms
memory: 3832kb
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: 3912kb
input:
1 0 2 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3964kb
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: 3800kb
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: 1ms
memory: 3840kb
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:
34826804 763875883 763875883 763875883 763875883 763875883 763875883 763875883 248820103 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 763875883 7...
result:
wrong answer 104th numbers differ - expected: '763875883', found: '807426271'