QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[2024-04-30 23:45:19]
评测

测评结果：WA
用时：1ms
内存：3964kb

查看

[2024-04-30 23:45:19]
提交

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

*/

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3780kb

input:

output:

1 2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3960kb

input:

output:

2 4 3 1

result:

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

Test #3:

score: 0

Accepted

time: 0ms

memory: 3832kb

input:

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:

output:

2 1

result:

ok 2 number(s): "2 1"

Test #6:

score: 0

Accepted

time: 0ms

memory: 3800kb

input:

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:

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'