QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#396994	#6742. Leaves	skulker	RE	6ms	21440kb	C++20	3.4kb	2024-04-23 15:18:08	2024-04-23 15:18:08

Judging History

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

[2024-04-23 15:18:08]
评测

测评结果：RE
用时：6ms
内存：21440kb

查看

[2024-04-23 15:18:08]
提交

answer

#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
int n,m;
string dp[1100][510];
//vector<int> len[1100][510];

int lf[110];
int siz[1100];

vector<int> nex[1100];
string val[1100];

void dfs(int now){
    siz[now]=1;
    lf[now]=0;
    if(nex[now].size()==0){
        lf[now]=1;
        dp[now][0]=val[now]+" ";
//        len[now][0].push_back(val[now].size());
        return ;
    }
    else {
        for(int i=0;i<nex[now].size();i++){
            dfs(nex[now][i]);
            siz[now]=siz[now]+siz[nex[now][i]];
            lf[now]=lf[now]+lf[nex[now][i]];
        }
    }
    int l=nex[now][0],r=nex[now][1];
    for(int i=0;i<=(siz[l]-1)/2;i++){
        for(int j=0;j<=(siz[r]-1)/2&&i+j<=m;j++){
            string s2=dp[l][i]+dp[r][j];
            if(dp[now][i+j].size()==0){
                dp[now][i+j]=s2;
//                for(int k=0;k<len[l][i].size();k++){
//                    len[now][i+j].push_back(len[l][i][k]);
//                }
//                for(int k=0;k<len[r][j].size();k++){
//                    len[now][i+j].push_back(len[r][j][k]);
//                }
            }
            else {
                if(dp[now][i+j]>s2) {
                    dp[now][i+j]=s2;
//                    for(int k=0;k<len[l][i].size();k++){
//                        len[now][i+j].push_back(len[l][i][k]);
//                    }
//                    for(int k=0;k<len[r][j].size();k++){
//                        len[now][i+j].push_back(len[r][j][k]);
//                    }
                }
            }
        }
    }
    l=nex[now][1],r=nex[now][0];
    for(int i=0;i<=(siz[l]-1)/2;i++){
        for(int j=0;j<=(siz[r]-1)/2&&i+j+1<=m;j++){
            string s2=dp[l][i]+dp[r][j];
            if(dp[now][i+j+1].size()==0){
                dp[now][i+j+1]=s2;
//                for(int k=0;k<len[l][i].size();k++){
//                    len[now][i+j+1].push_back(len[l][i][k]);
//                }
//                for(int k=0;k<len[r][j].size();k++){
//                    len[now][i+j+1].push_back(len[r][j][k]);
//                }
            }
            else {
                if(dp[now][i+j+1]>s2) {
                    dp[now][i+j+1]=s2;
//                    for(int k=0;k<len[l][i].size();k++){
//                        len[now][i+j+1].push_back(len[l][i][k]);
//                    }
//                    for(int k=0;k<len[r][j].size();k++){
//                        len[now][i+j+1].push_back(len[r][j][k]);
//                    }
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    int u,v,w;
    int opt;
    for(int i=1;i<=n;i++){
        cin>>opt;
        if(opt==1){
            cin>>u>>v;
            nex[i].push_back(u);
            nex[i].push_back(v);
        }
        else {
            cin>>val[i];
        }
    }
    dfs(1);
    string ans=dp[1][m];
    int pos=m;
    for(int i=m-2;i>=0;i-=2){
        if(ans>dp[1][i]) {
            ans=dp[1][i];
            pos=i;
        }
    }
//    int k=len[1][pos][0];
    int cnt=0;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i];
//        k--;
//        if(k==0){
//            cout<<" ";
//            cnt++;
//            k=len[1][pos][cnt];
//        }
    }
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 5ms

memory: 21436kb

input:

output:

1 2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0

Accepted

time: 6ms

memory: 21440kb

input:

output:

2 4 3 1

result:

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

Test #3:

score: 0

Accepted

time: 0ms

memory: 21236kb

input:

output:

1 3 4 2

result:

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

Test #4:

score: 0

Accepted

time: 2ms

memory: 21204kb

input:

1 0
2 1000000000

output:

1000000000

result:

ok 1 number(s): "1000000000"

Test #5:

score: 0

Accepted

time: 0ms

memory: 21428kb

input:

output:

2 1

result:

ok 2 number(s): "2 1"

Test #6:

score: 0

Accepted

time: 0ms

memory: 21060kb

input:

output:

1 2 3 4

result:

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

Test #7:

score: -100

Runtime Error

input: