QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409103#7684. Sweet Sugarlight_ink_dots#WA 131ms40744kbC++143.0kb2024-05-11 18:52:042024-05-11 18:52:05

Judging History

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

  • [2024-05-11 18:52:05]
  • 评测
  • 测评结果：WA
  • 用时：131ms
  • 内存：40744kb
查看
  • [2024-05-11 18:52:04]
  • 提交

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) up[x]=1e9;
            // else{
            //     int sum=0,mx=0;
            //     for(int y:v[x]){
            //         if(y==dad[x]) continue;
            //         if(minsz[y]==1e9){
            //             sum+=w[y];mx=max(mx,w[y]);
            //             continue;
            //         }
            //     }
            //     if(tiks==0) up[x]=sum+1-mx; 
            //     else 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();

}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 40744kb

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: 0ms
memory: 40692kb

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: 0
Accepted
time: 131ms
memory: 38372kb

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:

ok 200000 numbers

Test #4:

score: -100
Wrong Answer
time: 131ms
memory: 40556kb

input:

100000
10 16
0 1 0 1 0 1 1 0 1 1
4 10
3 10
9 1
4 7
5 2
9 5
6 9
2 3
8 4
10 18
1 0 0 1 0 0 1 1 0 2
5 1
4 2
5 3
3 4
2 10
4 9
3 8
7 3
6 5
10 13
0 1 0 1 0 1 1 0 1 1
5 2
4 3
1 6
8 9
1 8
3 5
9 4
7 6
3 10
10 16
1 0 1 0 1 1 1 0 1 1
6 8
2 4
9 6
2 6
4 10
5 3
1 6
8 7
3 6
10 13
0 0 0 0 1 0 1 0 1 0
2 1
2 7
7 9
7 ...

output:

0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
1
0
1
1
0
0
0
1
0
0
0
0
0
0
3
2
3
1
0
2
0
0
1
0
0
2
5
1
0
2
1
0
0
1
0
0
1
1
0
1
0
1
7
0
1
1
0
0
1
1
8
1
0
1
1
1
1
0
1
1
4
0
1
0
0
0
3
0
0
2
1
10
1
1
0
2
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
7
0
0
2
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
5
0
6
1
2
0
1
0
0
0
0
4
1
0
0
0
7
0...

result:

wrong answer 33rd numbers differ - expected: '2', found: '3'
English 繁體中文 简体中文

Server Time: 2024-12-05 00:57:25 | OpenSource Project