oj.uz

Submission #641678

# Submission time Handle Problem Language Result Execution time Memory
641678 2022-09-17T12:18:10 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 391 ms 18436 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 <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 = 2;
    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:176:39: warning: unused variable 'noduri' [-Wunused-variable]
  176 |         int nou = leaves + k, kk = k, noduri = n - 1 + k;
      |                                       ^~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 137 ms 4624 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3616 KB Output is correct
2 Correct 65 ms 3540 KB Output is correct
3 Correct 83 ms 11616 KB Output is correct
4 Correct 110 ms 10260 KB Output is correct
5 Correct 133 ms 11844 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4184 KB Output is correct
2 Correct 56 ms 4148 KB Output is correct
3 Correct 49 ms 18436 KB Output is correct
4 Correct 148 ms 18016 KB Output is correct
5 Correct 42 ms 17256 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4976 KB Output is correct
2 Correct 71 ms 4580 KB Output is correct
3 Correct 21 ms 4564 KB Output is correct
4 Correct 14 ms 5104 KB Output is correct
5 Correct 20 ms 4948 KB Output is correct
6 Correct 71 ms 5092 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 7996 KB Output is correct
2 Correct 352 ms 7760 KB Output is correct
3 Correct 240 ms 5252 KB Output is correct
4 Correct 391 ms 7964 KB Output is correct
5 Correct 321 ms 7808 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 11724 KB Output is correct
2 Correct 143 ms 15400 KB Output is correct
3 Correct 202 ms 14448 KB Output is correct
4 Correct 205 ms 13972 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 137 ms 4624 KB Output is correct
3 Correct 65 ms 3616 KB Output is correct
4 Correct 65 ms 3540 KB Output is correct
5 Correct 83 ms 11616 KB Output is correct
6 Correct 110 ms 10260 KB Output is correct
7 Correct 133 ms 11844 KB Output is correct
8 Correct 56 ms 4184 KB Output is correct
9 Correct 56 ms 4148 KB Output is correct
10 Correct 49 ms 18436 KB Output is correct
11 Correct 148 ms 18016 KB Output is correct
12 Correct 42 ms 17256 KB Output is correct
13 Correct 118 ms 4976 KB Output is correct
14 Correct 71 ms 4580 KB Output is correct
15 Correct 21 ms 4564 KB Output is correct
16 Correct 14 ms 5104 KB Output is correct
17 Correct 20 ms 4948 KB Output is correct
18 Correct 71 ms 5092 KB Output is correct
19 Correct 241 ms 7996 KB Output is correct
20 Correct 352 ms 7760 KB Output is correct
21 Correct 240 ms 5252 KB Output is correct
22 Correct 391 ms 7964 KB Output is correct
23 Correct 321 ms 7808 KB Output is correct
24 Correct 346 ms 11724 KB Output is correct
25 Correct 143 ms 15400 KB Output is correct
26 Correct 202 ms 14448 KB Output is correct
27 Correct 205 ms 13972 KB Output is correct
28 Correct 234 ms 7628 KB Output is correct
29 Correct 226 ms 14596 KB Output is correct
30 Correct 147 ms 11756 KB Output is correct
31 Correct 134 ms 17956 KB Output is correct
32 Correct 334 ms 7756 KB Output is correct
33 Correct 209 ms 11988 KB Output is correct
34 Correct 212 ms 13660 KB Output is correct
35 Correct 193 ms 15148 KB Output is correct