Submission #641675

#	Time	Username	Problem	Language	Result	Execution time	Memory
641675		Vladth11	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	399 ms	24912 KiB

cleaning

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 200001;
const ll VMAX = 101;
const ll INF = 2e9;
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 24;
const ll inv2 = 500000004;

ll leaves;

vector <ll> v[NMAX];
ll sz[NMAX];
ll parent[NMAX];
ll boss[NMAX];
ll root = 1;
ll stamp;
pii timp[NMAX];

void getSize(ll node, ll p) {
    sz[node] = 1;
    parent[node] = p;
    for(auto x : v[node]) {
        if(x == p) continue;
        getSize(x, node);
        sz[node] += sz[x];
    }
}

void heavy(ll node, ll p, ll capat) {
    boss[node] = capat;
    timp[node].first = ++stamp;
    ll maxim = -1;
    for(auto x : v[node]) {
        if(x == p) continue;
        if(maxim == -1 || sz[maxim] < sz[x]) {
            maxim = x;
        }
    }
    if(maxim != -1) {
        heavy(maxim, node, capat);
        for(auto x : v[node]) {
            if(x == p || x == maxim) continue;
            heavy(x, node, x);
        }
    }
    timp[node].second = stamp;
}

struct Node{
    ll pare, impare, lazy;
}all[NMAX * 4];

Node combine(Node a, Node b){
    Node sol;
    sol.pare = a.pare + b.pare;
    sol.impare = a.impare + b.impare;
    sol.lazy = 0; /// doar sa nu fie 1
    return sol;
}

void propaga(ll node, ll st, ll dr){
    if(st != dr){
        all[node * 2].lazy ^= all[node].lazy;
        all[node * 2 + 1].lazy ^= all[node].lazy;
    }
    if(all[node].lazy == 1){
        swap(all[node].pare, all[node].impare);
    }
    all[node].lazy = 0;
}

void update(ll node, ll st, ll dr, ll a, ll b){
    propaga(node, st, dr);
    if(a <= st && dr <= b){
        all[node].lazy ^= 1;
        return;
    }
    ll mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b);
    if(b > mid)
        update(node * 2 + 1, mid + 1, dr, a, b);
    propaga(node * 2, st, mid);
    propaga(node * 2 + 1, mid + 1, dr);
    all[node] = combine(all[node * 2], all[node * 2 + 1]);
}

ll cine(ll node, ll st, ll dr, ll a){
    propaga(node, st, dr);
    if(st == dr){
        if(all[node].pare)
            return 0;
        return 1;
    }
    ll mid = (st + dr) / 2;
    if(a <= mid){
        return cine(node * 2, st, mid, a);
    }
    return cine(node * 2 + 1, mid + 1, dr, a);
}

void build(ll node, ll st, ll dr){
    if(st == dr){
        all[node].pare = 1;
        all[node].impare = 0;
        all[node].lazy = 0;
        return;
    }
    ll mid = (st + dr) / 2;
    build(node * 2, st, mid);
    build(node * 2 + 1, mid + 1, dr);
    all[node] = combine(all[node * 2], all[node * 2 + 1]);
}

ll n;
ll avem[NMAX];

pii query(){
    propaga(1, 1, n);
    pii x = {all[1].pare, all[1].impare};
    ll primul = cine(1, 1, n, timp[root].first);
    if(primul == 0)
        x.first--;
    else
        x.second--;
    return x;
}

void turn(ll node){
    while(node != 0){
        update(1, 1, n, timp[boss[node]].first, timp[node].first);
        node = parent[boss[node]];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll q, i;
    cin >> n >> q;
    for(i = 1; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i = 1; i <= n; i++) {
        if(v[i].size() > 1)
            root = i;
        else
            leaves++;
    }
    root = 1;
    getSize(root, 0);
    heavy(root, 0, root);
    build(1, 1, n);
    for(i = 1; i <= n; i++){
        if(v[i].size() == 1){
            turn(i);
        }
    }
    while(q--){
        ll k;
        cin >> k;
        ll nou = leaves + k, kk = k, noduri = n - 1 + k;
        vector <ll> toReverse;
        while(k--){
            ll x;
            cin >> x;
            if(v[x].size() == 1 && avem[x] != (q + 1)){
                nou--;
                avem[x] = (q + 1);
            }else{
                turn(x);
                toReverse.push_back(x);
            }
        }
        if(nou % 2 == 1){
            cout << -1 << "\n";
        }else{
            pii x = query();
            x.second += kk;
            cout << x.first * 2 + x.second << "\n";
        }
        for(auto x : toReverse){
            turn(x);
        }
    }
    return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:176:38: warning: unused variable 'noduri' [-Wunused-variable]
  176 |         ll nou = leaves + k, kk = k, noduri = n - 1 + k;
      |                                      ^~~~~~

• 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