QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402800 | #6742. Leaves | altaires1 | ML | 246ms | 33964kb | C++14 | 2.9kb | 2024-05-01 15:22:19 | 2024-05-01 15:22:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1100;
int n,m;
int into[maxn];
int arrayA[maxn];
vector<int> dp[maxn][maxn];
vector<int> to[maxn];
int siz[maxn];
void dfs1(int a){
if(to[a].empty()){
siz[a]=0;
return;
}
siz[a]=1;
for(int it : to[a]){
dfs1(it);
siz[a]+=siz[it];
}
return;
}
void dfs(int a){
if(to[a].empty()){
dp[a][0].push_back(arrayA[a]);
return;
}
int l=to[a][0];
int r=to[a][1];
dfs(l);
dfs(r);
for(int i=0;i<=siz[l];i++){
for(int j=0;j<=siz[r];j++){
//先左后右,表示没有交换
vector<int> temp;
int len=0;
for(int it : dp[l][i]){
temp.push_back(it);
len++;
}
for(int it : dp[r][j]){
temp.push_back(it);
len++;
}
if(dp[a][i+j].empty()){
for(int it : temp){
dp[a][i+j].push_back(it);
}
}
else{
int judge=0;
for(int k=0;k<len;k++){
if(dp[a][i+j][k]<temp[k]){
judge=-1;
break;
}
else if(dp[a][i+j][k]>temp[k]){
judge=1;
break;
}
}
if(judge==1){
dp[a][i+j].clear();
for(int it : temp){
dp[a][i+j].push_back(it);
}
}
}
//先右后左,表示交换
if(i+j+1>siz[a]){
continue;
}
temp.clear();
len=0;
for(int it : dp[r][j]){
temp.push_back(it);
len++;
}
for(int it : dp[l][i]){
temp.push_back(it);
len++;
}
if(dp[a][i+j+1].empty()){
for(int it : temp){
dp[a][i+j+1].push_back(it);
}
}
else{
int judge=0;
for(int k=0;k<len;k++){
if(dp[a][i+j+1][k]<temp[k]){
judge=-1;
break;
}
else if(dp[a][i+j+1][k]>temp[k]){
judge=1;
break;
}
}
if(judge==1){
dp[a][i+j+1].clear();
for(int it : temp){
dp[a][i+j+1].push_back(it);
}
}
}
}
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
int type;
cin>>type;
if(type==1){
int l,r;
cin>>l>>r;
into[l]++;
into[r]++;
to[i].push_back(l);
to[i].push_back(r);
}
else{
cin>>arrayA[i];
}
}
int root=0;
for(int i=1;i<=n;i++){
if(into[i]==0){
root=i;
break;
}
}
dfs1(root);
dfs(root);
vector<int> ans;
int len=dp[root][0].size();
for(int i=0;i<=siz[root]&&i<=m;i++){
if((m-i)%2==0){
if(ans.empty()){
for(int it : dp[root][i]){
ans.push_back(it);
}
}
else{
int judge=0;
for(int k=0;k<len;k++){
if(ans[k]<dp[root][i][k]){
judge=-1;
break;
}
else if(ans[k]>dp[root][i][k]){
judge=1;
break;
}
}
if(judge==1){
ans.clear();
for(int it : dp[root][i]){
ans.push_back(it);
}
}
}
}
}
for(int it : ans){
cout<<it<<' ';
}
cout<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 32224kb
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: 6ms
memory: 32220kb
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: 9ms
memory: 32144kb
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: 6ms
memory: 31964kb
input:
1 0 2 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #5:
score: 0
Accepted
time: 0ms
memory: 31884kb
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: 3ms
memory: 31932kb
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: 0
Accepted
time: 213ms
memory: 33784kb
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:
ok 500 numbers
Test #8:
score: 0
Accepted
time: 236ms
memory: 33964kb
input:
999 480 1 2 3 1 4 5 1 7 6 1 8 9 1 10 11 1 13 12 1 15 14 1 17 16 1 19 18 1 21 20 1 23 22 1 24 25 1 26 27 1 28 29 1 31 30 1 32 33 1 34 35 1 37 36 1 38 39 1 41 40 1 42 43 1 44 45 1 46 47 1 48 49 1 51 50 1 52 53 1 54 55 1 57 56 1 58 59 1 60 61 1 62 63 1 65 64 1 66 67 1 69 68 1 71 70 1 72 73 1 75 74 1 77...
output:
530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 530024839 ...
result:
ok 500 numbers
Test #9:
score: 0
Accepted
time: 233ms
memory: 33872kb
input:
999 480 1 3 2 1 5 4 1 7 6 1 8 9 1 10 11 1 13 12 1 15 14 1 17 16 1 18 19 1 21 20 1 23 22 1 25 24 1 26 27 1 29 28 1 31 30 1 33 32 1 34 35 1 37 36 1 38 39 1 41 40 1 43 42 1 45 44 1 47 46 1 49 48 1 50 51 1 52 53 1 54 55 1 56 57 1 59 58 1 60 61 1 62 63 1 65 64 1 67 66 1 69 68 1 71 70 1 73 72 1 74 75 1 76...
output:
507922 928353918 51892154 809031414 296508656 801553730 385852006 930053625 95913518 431154803 117002192 187199343 405980569 664093190 478863675 930428963 3440725 490128679 92302056 563992614 27927487 246777697 168388113 922508131 52386784 780998040 438167217 876407248 158186938 633166175 788275543 ...
result:
ok 500 numbers
Test #10:
score: 0
Accepted
time: 246ms
memory: 33800kb
input:
999 480 1 3 2 1 4 5 1 7 6 1 8 9 1 10 11 1 13 12 1 15 14 1 16 17 1 19 18 1 21 20 1 23 22 1 24 25 1 26 27 1 29 28 1 30 31 1 32 33 1 35 34 1 37 36 1 38 39 1 41 40 1 43 42 1 45 44 1 46 47 1 48 49 1 50 51 1 52 53 1 54 55 1 56 57 1 58 59 1 60 61 1 63 62 1 65 64 1 66 67 1 68 69 1 70 71 1 72 73 1 74 75 1 76...
output:
666292 26210483 65023030 95745223 11431606 30237589 40996997 59830702 14512182 24640163 39361368 85684143 17020177 58437715 74457645 91998540 7557034 46923480 16066480 33921131 14512182 83949838 22501176 83949838 15127734 18414338 52979072 81930757 24640163 70913581 72929459 78973167 3687875 4610266...
result:
ok 500 numbers
Test #11:
score: 0
Accepted
time: 232ms
memory: 33836kb
input:
999 480 1 3 2 1 4 5 1 7 6 1 9 8 1 10 11 1 13 12 1 15 14 1 16 17 1 18 19 1 20 21 1 23 22 1 24 25 1 27 26 1 29 28 1 30 31 1 33 32 1 34 35 1 37 36 1 39 38 1 40 41 1 42 43 1 44 45 1 47 46 1 48 49 1 50 51 1 52 53 1 55 54 1 56 57 1 59 58 1 60 61 1 62 63 1 64 65 1 66 67 1 68 69 1 70 71 1 72 73 1 75 74 1 77...
output:
874376 19021636 10912872 49114704 21454471 94310772 60086613 88323254 20181141 62658098 54568372 64872279 21454471 30659919 73483837 98385133 12300384 74080822 54568372 100102768 29770805 62658098 33159023 62908008 33159023 98943188 52580720 64872279 58787422 98644936 73687255 98385133 10912872 9838...
result:
ok 500 numbers
Test #12:
score: -100
Memory Limit Exceeded
input:
905 52 1 3 2 2 25780328 1 4 5 2 84996992 1 6 7 2 43060692 1 8 9 2 58356233 1 11 10 2 48172306 1 12 13 2 94654986 1 14 15 2 66085196 1 17 16 2 43141873 1 18 19 2 58356233 1 21 20 2 58356233 1 22 23 2 64124892 1 24 25 2 55464563 1 27 26 2 46324683 1 29 28 2 78919648 1 30 31 2 13379324 1 32 33 2 960564...
output:
612429 612429 11385745 15524596 27354220 30826255 44403070 95193352 30760083 84996992 87443977 43060692 49958425 13964121 91042474 36461317 15704020 17411083 64017133 36129702 78978485 64017133 17411083 36057170 100691869 58356233 19600883 97205832 56442997 15704020 11168414 91042474 36057170 789196...