oj.uz

Submission #641674

# Submission time Handle Problem Language Result Execution time Memory
641674 2022-09-17T12:16:10 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 540 ms 19608 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 = 100001;
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++;
    }
    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--){
        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:175:39: warning: unused variable 'noduri' [-Wunused-variable]
  175 |         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 2644 KB Output is correct
2 Correct 182 ms 5352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3920 KB Output is correct
2 Correct 82 ms 3964 KB Output is correct
3 Correct 124 ms 12480 KB Output is correct
4 Correct 146 ms 11324 KB Output is correct
5 Correct 167 ms 13132 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 4504 KB Output is correct
2 Correct 66 ms 4560 KB Output is correct
3 Correct 48 ms 19608 KB Output is correct
4 Correct 154 ms 19496 KB Output is correct
5 Correct 54 ms 18292 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 6004 KB Output is correct
2 Correct 71 ms 4856 KB Output is correct
3 Correct 24 ms 4708 KB Output is correct
4 Correct 19 ms 5180 KB Output is correct
5 Correct 33 ms 5380 KB Output is correct
6 Correct 92 ms 5488 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 9344 KB Output is correct
2 Correct 470 ms 9060 KB Output is correct
3 Correct 336 ms 6220 KB Output is correct
4 Correct 403 ms 9136 KB Output is correct
5 Correct 540 ms 9124 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 13632 KB Output is correct
2 Correct 256 ms 16228 KB Output is correct
3 Correct 294 ms 15352 KB Output is correct
4 Correct 255 ms 16516 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 182 ms 5352 KB Output is correct
3 Correct 80 ms 3920 KB Output is correct
4 Correct 82 ms 3964 KB Output is correct
5 Correct 124 ms 12480 KB Output is correct
6 Correct 146 ms 11324 KB Output is correct
7 Correct 167 ms 13132 KB Output is correct
8 Correct 77 ms 4504 KB Output is correct
9 Correct 66 ms 4560 KB Output is correct
10 Correct 48 ms 19608 KB Output is correct
11 Correct 154 ms 19496 KB Output is correct
12 Correct 54 ms 18292 KB Output is correct
13 Correct 126 ms 6004 KB Output is correct
14 Correct 71 ms 4856 KB Output is correct
15 Correct 24 ms 4708 KB Output is correct
16 Correct 19 ms 5180 KB Output is correct
17 Correct 33 ms 5380 KB Output is correct
18 Correct 92 ms 5488 KB Output is correct
19 Correct 326 ms 9344 KB Output is correct
20 Correct 470 ms 9060 KB Output is correct
21 Correct 336 ms 6220 KB Output is correct
22 Correct 403 ms 9136 KB Output is correct
23 Correct 540 ms 9124 KB Output is correct
24 Correct 375 ms 13632 KB Output is correct
25 Correct 256 ms 16228 KB Output is correct
26 Correct 294 ms 15352 KB Output is correct
27 Correct 255 ms 16516 KB Output is correct
28 Correct 426 ms 8816 KB Output is correct
29 Correct 302 ms 15500 KB Output is correct
30 Correct 148 ms 13076 KB Output is correct
31 Correct 163 ms 19532 KB Output is correct
32 Correct 441 ms 9200 KB Output is correct
33 Correct 231 ms 14120 KB Output is correct
34 Correct 312 ms 16208 KB Output is correct
35 Correct 241 ms 16076 KB Output is correct