oj.uz

Submission #759013

# Submission time Handle Problem Language Result Execution time Memory
759013 2023-06-15T16:43:52 Z gagik_2007 Spring cleaning (CEOI20_cleaning) C++17
28 / 100
 1000 ms 11256 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

#pragma GCC optimize("O2")

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 7;
ll n, m, k;
ll p[N];
vector<int>g[N];
bool is_leaf[N];
int leaf_cnt[N];

void dfs(int v, int par){
    is_leaf[v]=(g[v].size()==1);
    leaf_cnt[v]=is_leaf[v];
    p[v]=par;
    for(int to:g[v]){
        if(to!=par){
            dfs(to,v);
            leaf_cnt[v]+=leaf_cnt[to];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1);
    int cc=leaf_cnt[1];
    int ans=0;
    for(int v=2;v<=n;v++){
        if(leaf_cnt[v]%2==0){
            ans+=2;
            // cout<<v<<endl;
        }
        else{
            ans++;
        }
    }
    vector<int>was_leaf;
    vector<int>lconi;
    for(int i=0;i<m;i++){
        // cout<<ans<<endl;
        int d;
        cin>>d;
        for(int j=0;j<d;j++){
            int v;
            cin>>v;
            if(is_leaf[v]){
                was_leaf.push_back(v);
                is_leaf[v]=false;
                ans++;
            }
            else{
                ans++;
                cc++;
                lconi.push_back(v);
                while(v!=1){
                    // cout<<v<<endl;
                    if(leaf_cnt[v]%2==0){
                        ans-=2;
                    }
                    else{
                        ans--;
                    }
                    leaf_cnt[v]++;
                    if(leaf_cnt[v]%2==0){
                        ans+=2;
                    }
                    else{
                        ans++;
                    }
                    v=p[v];
                }
            }
        }
        if(cc%2==0)cout<<ans<<endl;
        else cout<<-1<<endl;
        for(int v:lconi){
            ans--;
            cc--;
            while(v!=1){
                if(leaf_cnt[v]%2==0){
                    ans-=2;
                }
                else{
                    ans--;
                }
                leaf_cnt[v]--;
                if(leaf_cnt[v]%2==0){
                    ans+=2;
                }
                else{
                    ans++;
                }
                v=p[v];
            }
        }
        lconi.clear();
        for(int v:was_leaf){
            is_leaf[v]=true;
            ans--;
        }
        was_leaf.clear();
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 24 ms 4344 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3864 KB Output is correct
2 Correct 7 ms 3904 KB Output is correct
3 Correct 18 ms 8268 KB Output is correct
4 Correct 19 ms 7712 KB Output is correct
5 Correct 26 ms 9164 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1006 ms 4304 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 1067 ms 4812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7044 KB Output is correct
2 Correct 37 ms 6868 KB Output is correct
3 Correct 28 ms 5000 KB Output is correct
4 Correct 38 ms 6952 KB Output is correct
5 Correct 39 ms 6860 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 9480 KB Output is correct
2 Execution timed out 1095 ms 11256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 24 ms 4344 KB Output is correct
3 Correct 7 ms 3864 KB Output is correct
4 Correct 7 ms 3904 KB Output is correct
5 Correct 18 ms 8268 KB Output is correct
6 Correct 19 ms 7712 KB Output is correct
7 Correct 26 ms 9164 KB Output is correct
8 Execution timed out 1006 ms 4304 KB Time limit exceeded
9 Halted 0 ms 0 KB -