Submission #1270221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270221		huyngodzz	Spring cleaning (CEOI20_cleaning)	C++20	25 / 100	1094 ms	25156 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
#define FOR(i , a, b) for(int i = a; i <= b ; i++)
#define REP(i , a, b) for(int i = b; i >= a ; i--)
#define ALL(v) v.begin() , v.end()
#define F first
#define pb push_back
#define S second
bool maximize(int& x,int y){
    if(x < y){
        x = y;
        return 1;
    }
    return 0;
}
bool maximizell(long long & x,long long  y){
    if(x < y){
        x = y;
        return 1;
    }
    return 0;
}
bool minimize(int& x,int y){
    if(x > y){
        x = y;
        return 1;
    }
    return 0;
}
bool minimizell(long long & x,long long  y){
    if(x > y){
        x = y;
        return 1;
    }
    return 0;
}

const int maxN =  1e5 + 999;
int n , q, sz[maxN];
vector<int> event[maxN];
vector<int> e[maxN];
pair<int ,int > Edge[maxN];
namespace sub1{
    int vis[maxN];
    bool check(){
        FOR(i, 2, n){
            int u = Edge[i].F , v = Edge[i].S;
            if(u != 1 && v != 1)return 0;
        }
        return 1;
    }
    void solve(){
        int leaves = n - 1;
        int cost = n - 1;
        FOR(i, 1, q){
            for(auto x : event[i]){
                if(vis[x] == 0)vis[x] = 1;
                else ++leaves;
                ++cost;
            }
            if( (leaves  % 2 ) == 1){
                cout << -1 << '\n';
            }else{
                cout << cost << '\n';
            }

            for(auto x : event[i]){
                if(vis[x] == 1)vis[x] = 0;
                else --leaves;
                --cost;

            }
        }

    }
}
namespace sub2{
    int leaf[maxN] ,cnt, mark[maxN];
    void pre(int u ,int p){
        leaf[u] = 0;
//        cout << u << " ";
        for(auto x :e[u]){
//                cout << x<< " ";
            if(x == p)continue;
            pre(x, u);

        }
//        cout << u << " " ;
        if(e[u].size() == 1){
            leaf[u] = 1;
            ++cnt;
        }

    }
    int ans = 0;
    vector<int> dp[maxN];
    void dfs(int u ,int p){
        for(auto x : e[u]){
            if(x == p)continue;
            dfs(x, u);
            for(auto kk : dp[x]){
                dp[u].pb(kk + 1);
            }
        }
        while(dp[u].size() >= 3){
            int x = dp[u].back();
            dp[u].pop_back();
            int y = dp[u].back();
            ans += x + y;
            dp[u].pop_back();
        }
        if(p == 0){
            while(dp[u].size()){
                int x = dp[u].back();
                dp[u].pop_back();
                int y = dp[u].back();
                ans += x + y;
                dp[u].pop_back();
            }

        }
    }
    void solve(){
        int root = -1;
        FOR(i, 1, n){
            if(e[i].size() >= 2)root = i;
            if(root != -1)break;
        }
//        cout << root;
        FOR(i, 1, q){
            ans = 0;
            cnt = 0;
            pre(root, 0);

            for(auto x : event[i]){
                if(leaf[x] == 1 && mark[x] == 0)mark[x] = 1;
                else if(leaf[x] == 0 &&  mark[x] == 1)++cnt;
                else if(leaf[x] == 0)++cnt;
                leaf[x] = 0;
                dp[x].pb(1);
            }
//            cout << cnt << " ";
            if( (cnt % 2) == 1)cout << -1 << '\n';
            else{
                FOR(u, 1, n)if(leaf[u])dp[u].pb(0);
                dfs(root , 0);
                cout <<ans << '\n';
            }
            FOR(u, 1, n){
                dp[u].clear();
                mark[u] = 0;
            }


        }
//        cout << cnt;

    }
}
void solve(){
    cin >> n >> q;
    FOR(i, 2, n){
        int u ,v;
        cin >> u >> v;
        e[u].pb(v);
        e[v].pb(u);
        Edge[i] = {u , v};
    }
    FOR(i, 1 ,q){
        cin >> sz[i];
        FOR(x ,1 ,sz[i]){
            int u; cin >> u;
            event[i].pb(u);
        }
    }
    if(sub1::check())return sub1::solve();
    return sub2::solve();


}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("crt.inp", "r" , stdin);
//    freopen("crt.out", "w" ,stdout);
    int tc = 1;
    while(tc--)solve();
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30