Submission #1271739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271739		monaxia	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	177 ms	17476 KiB

cleaning

#include <bits/stdc++.h>
#include <ext/random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector

using namespace std;
using namespace __gnu_pbds; 

using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr ull Mod = 1e9 + 7;
constexpr ull Mod2 = 1 + 7 * 17 * (1 << 23);
constexpr ull sqr = 320;
constexpr ld eps = 1e-9;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r) {if(l <= r) return uniform_int_distribution <ll> (l, r)(rng); return -1;} 

int st[400005], lazy[400005];

void update111(int idx, int l, int r, int u, int v){
    if(lazy[idx] == 1){
        st[idx] = (r - l + 1) - st[idx];

        if(l != r){
            lazy[idx << 1] ^= 1;
            lazy[idx << 1 | 1] ^= 1; 
        }

        lazy[idx] = 0;
    }

    if(v < l || r < u) return;
    if(u <= l && r <= v){
        st[idx] = (r - l + 1) - st[idx];

        if(l != r){
            lazy[idx << 1] ^= 1;
            lazy[idx << 1 | 1] ^= 1;
        }

        return;
    }

    int mid = (l + r) >> 1;

    update111(idx << 1, l, mid, u, v);
    update111(idx << 1 | 1, mid + 1, r, u, v);

    st[idx] = st[idx << 1] + st[idx << 1 | 1];
}

int query111(int idx, int l, int r, int u, int v){
    if(lazy[idx] == 1){
        st[idx] = (r - l + 1) - st[idx];

        if(l != r){
            lazy[idx << 1] ^= 1;
            lazy[idx << 1 | 1] ^= 1; 
        }

        lazy[idx] = 0;
    }

    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[idx] + (r - l + 1 - st[idx]) * 2;

    int mid = (l + r) >> 1;

    return query111(idx << 1, l, mid, u, v) + query111(idx << 1 | 1, mid + 1, r, u, v);
}

void update(int l, int r){update111(1, 1, 100000, l, r);}
int query(int l, int r){return query111(1, 1, 100000, l, r);}

int n;

vector <int> graph[100005];
int h[100005], subtr[100005], parent[100005];
int heavy_p[100005];
int id[100005];

void dfs111(int node, int pr){
    h[node] = h[pr] + 1;
    subtr[node] = 1;
    parent[node] = pr;

    for(auto& x : graph[node]){
        if(x == pr) continue;
        dfs111(x, node);

        subtr[node] += subtr[x];
    }
}

int timer = 0;

void dfs222(int node, int pr){
    id[node] = ++ timer;

    pair <int, int> mx = {0, 0};

    for(auto& x : graph[node]){
        if(x == pr) continue;
        mx = max(mx, {subtr[x], x});
    }

    heavy_p[mx.sc] = heavy_p[node];
    if(mx.fr) dfs222(mx.sc, node);

    for(auto& x : graph[node]){
        if(x == mx.sc || x == pr) continue;
        heavy_p[x] = x;
        dfs222(x, node);
    }
}

void preprocess(){
    memset(st, 0, sizeof(st));
    memset(lazy, 0, sizeof(lazy));

    heavy_p[1] = 1;

    dfs111(1, 0);
    dfs222(1, 0);
}

void flip(int u){
    while(u){
        int next = (h[heavy_p[u]] >= 1) ? heavy_p[u] : 1;
        update(id[next], id[u]);
        u = parent[next];
    }
}

void solve(){
    int Q;
    cin >> n >> Q;

    int leafcnt = 0;

    int cnt[n + 1];
    memset(cnt, 0, sizeof(cnt));

    for(int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        graph[u].pb(v);
        graph[v].pb(u);
    }

    preprocess();

    for(int i = 1; i <= n; i ++){
        if(graph[i].size() == 1) flip(i), leafcnt ++;
    }

    while(Q --){
        int k, curleaf = 0;
        cin >> k;

        vector <int> cpr, flipped;

        for(int i = 1; i <= k; ++ i){
            int x;
            cin >> x;

            cnt[x] ++;
            cpr.pb(x);
        }

        sort(all(cpr));
        cpr.resize(unique(all(cpr)) - cpr.begin());

        for(auto& x : cpr) curleaf -= (graph[x].size() == 1) ? 1 : 0;

        if((leafcnt + curleaf + k) & 1){
            for(auto& x : cpr) cnt[x] = 0;
            cout << "-1\n";
            continue;
        }

        for(auto& x : cpr){
            if(graph[x].size() == 1 && !(cnt[x] & 1)){
                flip(x);
                flipped.pb(x);
                continue;
            }

            if(graph[x].size() != 1 && (cnt[x] & 1)){
                flip(x);
                flipped.pb(x);
            }
        }

        cout << st[1] + (n - st[1] - 1) * 2 + k << "\n";

        for(auto& x : cpr) cnt[x] = 0;
        for(auto& x : flipped) flip(x);
    }
} 

main(){
    // cout << 1; return 0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    if(fopen("Topic.inp", "r")){
        freopen("Topic.inp", "r", stdin);
        freopen("Topic.out", "w", stdout);
    }

    int t = 1;

    // cin >> t;

    while(t --){
        solve();
        cout << "\n";
    }
}



// Whose eyes are those eyes?

Compilation message (stderr)

cleaning.cpp:217:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  217 | main(){
      | ^~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:223:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |         freopen("Topic.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:224:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |         freopen("Topic.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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