oj.uz

Submission #963495

# Submission time Handle Problem Language Result Execution time Memory
963495 2024-04-15T07:17:46 Z Darren0724 Spring cleaning (CEOI20_cleaning) C++17
9 / 100
 1000 ms 17988 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
vector<int> adj[N],big(N,-1),sz(N,0),pa(N),deg(N,0);
vector<vector<int>> path(1);
void dfs(int k){
    if(deg[k]==1)sz[k]=1;
    for(int j:adj[k]){
        if(j==pa[k])continue;
        pa[j]=k;
        dfs(j);
        sz[k]+=sz[j];
        big[k]=(big[k]==-1||sz[big[k]]<sz[j]?j:big[k]);
    }
}   
void dfs2(int k){
    path.back().push_back(k);
    if(big[k]!=-1){
        dfs2(big[k]);
    }
    for(int j:adj[k]){
        if(j!=big[k]&&j!=pa[k]){
            path.push_back(vector<int>());
            dfs2(j);
        }
    }
}
void add(int p,int x){
    if(x==1&&deg[p]==1){
        sz[p]--;
    }
    if(x==-1&&deg[p]==1){
        sz[p]++;
    }
    for(int i=p;i>0;i=pa[i]){
        sz[i]+=x;
    }
}
int32_t main(){
    int n,q;cin>>n>>q;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int rt=1;
    for(int i=1;i<=n;i++){
        deg[i]=adj[i].size();
        if(deg[i]>=2)rt=i;
    }
    dfs(rt);
    dfs2(rt);
    for(int i=0;i<q;i++){
        int t;cin>>t;
        int ans=n-1+t;
        vector<int> a(t);
        for(int j=0;j<t;j++){
            cin>>a[j];
            add(a[j],1);
            deg[a[j]]++;
        }
        int leaves=t;
        for(int j=1;j<=n;j++){
            if(j==rt)continue;
            leaves+=(deg[j]==1);
            ans+=(sz[j]%2==0);
        }
        for(int j=0;j<t;j++){
            deg[a[j]]--;
            add(a[j],-1);
        }
        if(leaves&1){
            cout<<-1<<endl;
        }
        else{
            cout<<ans<<endl;
        }
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Incorrect 156 ms 9560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8796 KB Output is correct
2 Correct 18 ms 8792 KB Output is correct
3 Correct 50 ms 17988 KB Output is correct
4 Correct 60 ms 17168 KB Output is correct
5 Correct 69 ms 17620 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 9048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 10076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 12416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 14576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Incorrect 156 ms 9560 KB Output isn't correct
3 Halted 0 ms 0 KB -