QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #1176 | #742475 | #21624. 【PR #2】背包 | jqh333 | Ieihonglongyin | Success! | 2024-11-13 16:42:52 | 2024-11-13 16:42:52 |
详细
Extra Test:
Wrong Answer
time: 0ms
memory: 5200kb
input:
1 1000 30 8900 11100 164 162 164 208 197 173 181 179 190 209 160 161 207 187 196 168 153 177 190 208 159 164 175 187 200 198 164 190 188 171 169 149 203 167 152 199 203 163 191 151 158 165 193 183 164 161 152 199 151 175 208 173 199 160 171 189 205 155 167 165 184 203 173 204 195 200 194 209 196 182...
output:
0000000000000000001000000000000
result:
wrong answer 1st words differ - expected: '0000000000000000000000000000000', found: '0000000000000000001000000000000'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #742475 | #21624. 【PR #2】背包 | Ieihonglongyin | 97 | 327ms | 11976kb | C++14 | 1.5kb | 2024-11-13 16:40:55 | 2024-11-13 16:44:44 |
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N=1005,M=10;
int T,n,m;ll L,R,p[N],vi[N];vector<ll>f[N][55],tmp[55];vector<int>v[N];
void dfs(int u,int fa){for(int i=0;i<=m;i++)f[u][i].clear();f[u][0].push_back(0);
for(auto i:v[u])if(i!=fa){dfs(i,u),p[u]+=p[i];for(int j=0;j<m;j++)tmp[j].clear();
for(int a=0;a<m;a++)for(int b=0;a+b<m;b++)
for(auto x:f[u][a])for(auto y:f[i][b])tmp[a+b].push_back(x+y);
for(int j=0;j<m;j++){sort(tmp[j].begin(),tmp[j].end());
tmp[j].erase(unique(tmp[j].begin(),tmp[j].end()),tmp[j].end()),f[u][j].clear();
for(int k=0;k<min(M,(int)tmp[j].size());k++)f[u][j].push_back(tmp[j][k]);
for(int k=max(M,(int)tmp[j].size()-M);k<tmp[j].size();k++)f[u][j].push_back(tmp[j][k]);
}
}
for(int i=m-1;~i;i--)if(!f[u][i].empty()){int len=f[u][i].size();bool fl=0;for(auto j:f[u][i])fl|=L<=p[u]-j&&p[u]-j<=R;
if(len>=2*M){int tg1=0,tg2=0;
for(int j=1;j<M;j++)tg1+=f[u][i][j]-f[u][i][j-1]<=R-L;
for(int j=1;j<M;j++)tg2+=f[u][i][len-j]-f[u][i][len-j-1]<=R-L;
fl|=tg1+tg2>=17&&L<=p[u]-f[u][i][M-1]&&p[u]-f[u][i][len-M]<=R;
}if(fl)f[u][i+1].push_back(p[u]);
}
}
int main(){//freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>T;
while(T--){cin>>n>>m>>L>>R,m++;for(int i=1;i<=n;i++)cin>>p[i];
for(int x,y,i=1;i<n;i++)cin>>x>>y,v[x].push_back(y),v[y].push_back(x);dfs(1,0);
for(int i=1;i<=m;i++)cout<<(!f[1][i].empty()&&f[1][i].back()==p[1]);cout<<"\n";
for(int i=1;i<=n;i++)v[i].clear();
}
}