oj.uz

Submission #641675

# Submission time Handle Problem Language Result Execution time Memory
641675 2022-09-17T12:17:00 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 399 ms 24912 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 148 ms 8940 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7044 KB Output is correct
2 Correct 70 ms 6984 KB Output is correct
3 Correct 92 ms 20236 KB Output is correct
4 Correct 128 ms 18576 KB Output is correct
5 Correct 160 ms 20720 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 7600 KB Output is correct
2 Correct 53 ms 7664 KB Output is correct
3 Correct 53 ms 24912 KB Output is correct
4 Correct 133 ms 24820 KB Output is correct
5 Correct 63 ms 23628 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9464 KB Output is correct
2 Correct 57 ms 8584 KB Output is correct
3 Correct 23 ms 8472 KB Output is correct
4 Correct 16 ms 8564 KB Output is correct
5 Correct 21 ms 9196 KB Output is correct
6 Correct 66 ms 9044 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 14840 KB Output is correct
2 Correct 399 ms 14540 KB Output is correct
3 Correct 316 ms 10020 KB Output is correct
4 Correct 356 ms 14592 KB Output is correct
5 Correct 381 ms 14560 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20484 KB Output is correct
2 Correct 207 ms 23204 KB Output is correct
3 Correct 223 ms 21836 KB Output is correct
4 Correct 196 ms 22560 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 148 ms 8940 KB Output is correct
3 Correct 87 ms 7044 KB Output is correct
4 Correct 70 ms 6984 KB Output is correct
5 Correct 92 ms 20236 KB Output is correct
6 Correct 128 ms 18576 KB Output is correct
7 Correct 160 ms 20720 KB Output is correct
8 Correct 56 ms 7600 KB Output is correct
9 Correct 53 ms 7664 KB Output is correct
10 Correct 53 ms 24912 KB Output is correct
11 Correct 133 ms 24820 KB Output is correct
12 Correct 63 ms 23628 KB Output is correct
13 Correct 99 ms 9464 KB Output is correct
14 Correct 57 ms 8584 KB Output is correct
15 Correct 23 ms 8472 KB Output is correct
16 Correct 16 ms 8564 KB Output is correct
17 Correct 21 ms 9196 KB Output is correct
18 Correct 66 ms 9044 KB Output is correct
19 Correct 260 ms 14840 KB Output is correct
20 Correct 399 ms 14540 KB Output is correct
21 Correct 316 ms 10020 KB Output is correct
22 Correct 356 ms 14592 KB Output is correct
23 Correct 381 ms 14560 KB Output is correct
24 Correct 333 ms 20484 KB Output is correct
25 Correct 207 ms 23204 KB Output is correct
26 Correct 223 ms 21836 KB Output is correct
27 Correct 196 ms 22560 KB Output is correct
28 Correct 261 ms 13364 KB Output is correct
29 Correct 228 ms 22320 KB Output is correct
30 Correct 140 ms 20192 KB Output is correct
31 Correct 144 ms 24220 KB Output is correct
32 Correct 377 ms 14028 KB Output is correct
33 Correct 195 ms 19684 KB Output is correct
34 Correct 245 ms 22052 KB Output is correct
35 Correct 265 ms 21768 KB Output is correct