QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #409100 | #7684. Sweet Sugar | light_ink_dots# | WA | 133ms | 40740kb | C++14 | 2.8kb | 2024-05-11 18:46:02 | 2024-05-11 18:46:02 |
Judging History
answer
//ghost thread
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int N=1e6+100;
vector<int>v[N];
int n,k;
int dep[N],c[N],dad[N],w[N],up[N];
void dfs(int x,int fa){
dep[x]=dep[fa]+1;dad[x]=fa;
for(auto y:v[x]){
if(y==fa) continue;
dfs(y,x);
}
}
queue<int>q;
int minsz[N],ext[N];
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++) {
minsz[i]=1e9,w[i]=0,v[i].clear();
ext[i]=0;
}
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
int rt=0;
for(int i=1;i<=n;i++){
if(v[i].size()!=1) rt=i;
}
dfs(rt,0);
static int id[N];
for(int i=1;i<=n;i++) id[i]=i;
sort(id+1,id+1+n,[&](int u,int v){
return dep[u]>dep[v];
});
int ans=0;
for(int i=1;i<=n;i++){
int x=id[i];
for(int y:v[x]){
if(y==dad[x]) continue;
w[x]+=w[y];
minsz[x]=min(minsz[x],minsz[y]);
}
w[x]+=c[x];
if(c[x]==1) {
minsz[x]=min(w[x],minsz[x]);
int tiks=0;
for(int y:v[x]){
if(y==dad[x]) continue;
if(minsz[y]==1e9) continue;
tiks++;
}
if(tiks!=1||tiks==0) up[x]=1e9;
else{
int sum=0;
for(int y:v[x]){
if(y==dad[x]) continue;
if(minsz[y]==1e9){
sum+=w[y];
continue;
}
}
up[x]=sum+1;
}
}else{
int tiks=0;
for(int y:v[x]){
if(y==dad[x]) continue;
if(minsz[y]==1e9) continue;
tiks++;
}
if(tiks!=1||tiks==0) up[x]=1e9;
else{
int sum=0;
for(int y:v[x]){
if(y==dad[x]) continue;
if(minsz[y]==1e9){
sum+=w[y];
continue;
}
if(c[y]==1) up[x]=1;
else up[x]=up[y];
}
up[x]+=sum+c[x];
}
}
if((w[x]&1)==(k&1)&&w[x]>=k){
minsz[x]=1e9;
w[x]=0;ans++;up[x]=1e9;
continue;
}
if((w[x]&1)!=(k&1)&&(w[x]-min(up[x],minsz[x]))>=k){
minsz[x]=1e9;
w[x]=0;ans++;up[x]=1e9;
continue;
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 38608kb
input:
4 7 5 1 2 1 2 2 1 2 1 2 2 3 3 4 3 5 5 6 5 7 2 2 1 0 1 2 1 1 1 1 2 1
output:
2 0 1 0
result:
ok 4 number(s): "2 0 1 0"
Test #2:
score: 0
Accepted
time: 4ms
memory: 38608kb
input:
12 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 2 2 1 3 0 1 3 1 1 3 2 1 2000000 0 1 2000000 1 1 2000000 2
output:
0 1 0 0 0 1 0 0 0 0 0 0
result:
ok 12 numbers
Test #3:
score: -100
Wrong Answer
time: 133ms
memory: 40740kb
input:
200000 5 2 1 1 0 0 1 2 4 5 2 4 1 3 2 5 1 0 0 0 0 0 5 1 1 2 3 2 5 4 5 3 1 0 0 0 1 1 4 4 2 3 4 5 2 5 9 1 0 0 0 2 4 3 2 1 3 1 5 1 5 3 0 1 1 0 1 5 4 2 1 4 3 5 1 5 1 0 2 1 1 1 5 3 2 4 3 4 1 4 5 1 1 0 1 1 0 1 5 4 2 1 3 5 2 5 7 0 2 1 1 2 5 1 2 3 2 5 5 4 5 5 0 1 0 1 0 2 4 4 3 5 2 1 5 5 1 0 0 1 0 1 4 1 4 5 2...
output:
1 0 0 0 1 3 3 0 0 2 0 0 2 1 0 0 1 1 0 2 0 1 0 2 1 0 0 0 0 0 1 2 0 0 2 2 0 1 0 0 0 0 3 3 0 0 1 1 2 1 2 0 4 0 1 1 0 1 0 0 1 5 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 3 1 0 1 0 0 4 0 0 0 1 1 0 0 1 0 2 0 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 1 2 0 1 2 0 0 2 0 0 1 0 0 0 0 0 ...
result:
wrong answer 4270th numbers differ - expected: '0', found: '1'