QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #483322 | #6742. Leaves | ucup-team052# | WA | 0ms | 3940kb | C++14 | 2.7kb | 2024-07-18 15:33:37 | 2024-07-18 15:33:37 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define D(...) fprintf(stderr,__VA_ARGS__)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
using namespace std;
const int N=1005;
int n,m,type[N],lc[N],rc[N],a[N],sz[N];
vector<vector<int> >dp[2][N];
vector<int>tt[2][N];
vector<int>operator+(const vector<int>&lhs,const vector<int>&rhs){
vector<int>ret(SZ(lhs)+SZ(rhs));
rep(i,0,SZ(lhs)-1)ret[i]=lhs[i];
rep(i,SZ(lhs),SZ(ret)-1)ret[i]=rhs[i-SZ(lhs)];
return ret;
}
vector<int>Min(const vector<int>&lhs,const vector<int>&rhs){
if(lhs.empty())return rhs;
if(rhs.empty())return lhs;
assert(SZ(lhs)==SZ(rhs));
return min(lhs,rhs);
}
void solve(int u){
if(type[u]==1){
solve(lc[u]),solve(rc[u]);
sz[u]=sz[lc[u]]+sz[rc[u]];
dp[0][u].resize(sz[u]);
dp[1][u].resize(sz[u]);
rep(o0,0,1)if(!dp[o0][lc[u]].empty())rep(o1,0,1)if(!dp[o1][rc[u]].empty()){
rep(i,0,SZ(dp[o0][lc[u]])-1+SZ(dp[o1][rc[u]])-1){
vector<int>V0(dp[o0][lc[u]][i<SZ(dp[o0][lc[u]])?i:SZ(dp[o0][lc[u]])-1]);
vector<int>V1(dp[o1][rc[u]][i<SZ(dp[o0][lc[u]])?min(tt[o0][lc[u]][i],SZ(dp[o1][rc[u]])-1):i-SZ(dp[o0][lc[u]])+1]);
dp[(o0+o1)&1][u][(o0+o1)/2+i]=Min(dp[(o0+o1)&1][u][(o0+o1)/2+i],V0+V1);
}
}
swap(lc[u],rc[u]);
rep(o0,0,1)if(!dp[o0][lc[u]].empty())rep(o1,0,1)if(!dp[o1][rc[u]].empty()){
rep(i,0,SZ(dp[o0][lc[u]])-1+SZ(dp[o1][rc[u]])-1){
vector<int>V0(dp[o0][lc[u]][i<SZ(dp[o0][lc[u]])?i:SZ(dp[o0][lc[u]])-1]);
vector<int>V1(dp[o1][rc[u]][i<SZ(dp[o0][lc[u]])?min(tt[o0][lc[u]][i],SZ(dp[o1][rc[u]])-1):i-SZ(dp[o0][lc[u]])+1]);
dp[(o0+o1+1)&1][u][(o0+o1+1)/2+i]=Min(dp[(o0+o1+1)&1][u][(o0+o1+1)/2+i],V0+V1);
}
}
swap(lc[u],rc[u]);
rep(o,0,1){
while(dp[o][u].back().empty())dp[o][u].pop_back();
while(SZ(dp[o][u])>1&&dp[o][u].back()==dp[o][u][SZ(dp[o][u])-2])dp[o][u].pop_back();
}
rep(o,0,1){
dp[o][lc[u]].clear();
dp[o][lc[u]].shrink_to_fit();
dp[o][rc[u]].clear();
dp[o][rc[u]].shrink_to_fit();
tt[o][lc[u]].clear();
tt[o][lc[u]].shrink_to_fit();
tt[o][rc[u]].clear();
tt[o][rc[u]].shrink_to_fit();
}
rep(o,0,1){
tt[o][u].resize(SZ(dp[o][u]));
rep(i,1,SZ(tt[o][u])-1){
if(dp[o][u][i]==dp[o][u][i-1]){
tt[o][u][i]=tt[o][u][i-1]+1;
}else{
tt[o][u][i]=0;
}
}
}
}else{
dp[0][u].pb(vector<int>{a[u]});
tt[0][u].pb(0);
sz[u]=1;
}
}
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
cin>>n>>m;
rep(i,1,n){
cin>>type[i];
if(type[i]==1){
cin>>lc[i]>>rc[i];
}else{
cin>>a[i];
}
}
solve(1);
vector<int>ans(dp[m&1][1][min(m/2,SZ(dp[m&1][1])-1)]);
rep(i,0,SZ(ans)-1)printf("%d ",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3912kb
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: 3872kb
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: 3908kb
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: 3860kb
input:
1 0 2 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
3 1 1 2 3 2 1 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3940kb
input:
7 2 1 2 3 1 4 5 1 6 7 2 1 2 2 2 3 2 4
output:
2 1 4 3
result:
wrong answer 1st numbers differ - expected: '1', found: '2'