QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#402572	#6742. Leaves	mulberry^#	WA	0ms	3932kb	C++23	2.4kb	2024-04-30 22:28:10	2024-04-30 22:28:11

Judging History

你现在查看的是最新测评结果

[2024-04-30 22:28:11]
评测

测评结果：WA
用时：0ms
内存：3932kb

查看

[2024-04-30 22:28:10]
提交

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);
}
void print(int u){
    if(!L[u] && !R[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);
}
/*
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

*/

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3920kb

input:

output:

1 2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3932kb

input:

output:

2 4 3 1

result:

ok 4 number(s): "2 4 3 1"

Test #3:

score: 0

Accepted

time: 0ms

memory: 3920kb

input:

output:

1 3 4 2

result:

ok 4 number(s): "1 3 4 2"

Test #4:

score: 0

Accepted

time: 0ms

memory: 3892kb

input:

1 0
2 1000000000

output:

1000000000

result:

ok 1 number(s): "1000000000"

Test #5:

score: -100

Wrong Answer

time: 0ms

memory: 3824kb

input:

output:

1 2

result:

wrong answer 1st numbers differ - expected: '2', found: '1'