oj.uz

Submission #641650

# Submission time Handle Problem Language Result Execution time Memory
641650 2022-09-17T10:49:13 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 406 ms 22012 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
 
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
 
const int NMAX = 200001;
const int VMAX = 101;
const int INF = 2e9;
const int MOD = 1000000007;
const int BLOCK = 447;
const int base = 117;
const int nr_of_bits = 24;
const int inv2 = 500000004;
 
int leaves;
 
vector <int> v[NMAX];
int sz[NMAX];
int parent[NMAX];
int boss[NMAX];
int root = 1;
int stamp;
pii timp[NMAX];
 
void getSize(int node, int 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(int node, int p, int capat) {
    boss[node] = capat;
    timp[node].first = ++stamp;
    int 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{
    int pare, impare, lazy;
}aint[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(int node, int st, int dr){
    if(st != dr){
        aint[node * 2].lazy ^= aint[node].lazy;
        aint[node * 2 + 1].lazy ^= aint[node].lazy;
    }
    if(aint[node].lazy == 1){
        swap(aint[node].pare, aint[node].impare);
    }
    aint[node].lazy = 0;
}
 
void update(int node, int st, int dr, int a, int b){
    propaga(node, st, dr);
    if(a <= st && dr <= b){
        aint[node].lazy ^= 1;
        return;
    }
    int 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);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
 
int cine(int node, int st, int dr, int a){
    propaga(node, st, dr);
    if(st == dr){
        if(aint[node].pare)
            return 0;
        return 1;
    }
    int 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(int node, int st, int dr){
    if(st == dr){
        aint[node].pare = 1;
        aint[node].impare = 0;
        aint[node].lazy = 0;
        return;
    }
    int mid = (st + dr) / 2;
    build(node * 2, st, mid);
    build(node * 2 + 1, mid + 1, dr);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
 
int n;
int avem[NMAX];
 
pii query(){
    propaga(1, 1, n);
    pii x = {aint[1].pare, aint[1].impare};
    int primul = cine(1, 1, n, timp[root].first);
    if(primul == 0)
        x.first--;
    else
        x.second--;
    return x;
}
 
void turn(int 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);
    int q, i;
    cin >> n >> q;
    for(i = 1; i < n; i++) {
        int 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++;
    }
    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--){
        int k;
        cin >> k;
        int nou = leaves + k, kk = k, noduri = n - 1 + k;
        vector <int> toReverse;
        while(k--){
            int 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:174:39: warning: unused variable 'noduri' [-Wunused-variable]
  174 |         int nou = leaves + k, kk = k, noduri = n - 1 + k;
      |                                       ^~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 172 ms 7400 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 6276 KB Output is correct
2 Correct 79 ms 6316 KB Output is correct
3 Correct 94 ms 14792 KB Output is correct
4 Correct 127 ms 13700 KB Output is correct
5 Correct 176 ms 15620 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 6876 KB Output is correct
2 Correct 64 ms 6824 KB Output is correct
3 Correct 48 ms 21196 KB Output is correct
4 Correct 184 ms 20748 KB Output is correct
5 Correct 57 ms 20044 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 7764 KB Output is correct
2 Correct 66 ms 7320 KB Output is correct
3 Correct 27 ms 7072 KB Output is correct
4 Correct 20 ms 7468 KB Output is correct
5 Correct 23 ms 7564 KB Output is correct
6 Correct 72 ms 8000 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 10836 KB Output is correct
2 Correct 394 ms 11468 KB Output is correct
3 Correct 300 ms 8508 KB Output is correct
4 Correct 377 ms 11432 KB Output is correct
5 Correct 392 ms 11460 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 14540 KB Output is correct
2 Correct 180 ms 17384 KB Output is correct
3 Correct 274 ms 18160 KB Output is correct
4 Correct 224 ms 18636 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 172 ms 7400 KB Output is correct
3 Correct 91 ms 6276 KB Output is correct
4 Correct 79 ms 6316 KB Output is correct
5 Correct 94 ms 14792 KB Output is correct
6 Correct 127 ms 13700 KB Output is correct
7 Correct 176 ms 15620 KB Output is correct
8 Correct 69 ms 6876 KB Output is correct
9 Correct 64 ms 6824 KB Output is correct
10 Correct 48 ms 21196 KB Output is correct
11 Correct 184 ms 20748 KB Output is correct
12 Correct 57 ms 20044 KB Output is correct
13 Correct 130 ms 7764 KB Output is correct
14 Correct 66 ms 7320 KB Output is correct
15 Correct 27 ms 7072 KB Output is correct
16 Correct 20 ms 7468 KB Output is correct
17 Correct 23 ms 7564 KB Output is correct
18 Correct 72 ms 8000 KB Output is correct
19 Correct 290 ms 10836 KB Output is correct
20 Correct 394 ms 11468 KB Output is correct
21 Correct 300 ms 8508 KB Output is correct
22 Correct 377 ms 11432 KB Output is correct
23 Correct 392 ms 11460 KB Output is correct
24 Correct 343 ms 14540 KB Output is correct
25 Correct 180 ms 17384 KB Output is correct
26 Correct 274 ms 18160 KB Output is correct
27 Correct 224 ms 18636 KB Output is correct
28 Correct 282 ms 11212 KB Output is correct
29 Correct 254 ms 17716 KB Output is correct
30 Correct 150 ms 15524 KB Output is correct
31 Correct 148 ms 22012 KB Output is correct
32 Correct 406 ms 11428 KB Output is correct
33 Correct 189 ms 17100 KB Output is correct
34 Correct 300 ms 17452 KB Output is correct
35 Correct 255 ms 18380 KB Output is correct