oj.uz

Submission #641680

# Submission time Handle Problem Language Result Execution time Memory
641680 2022-09-17T12:18:53 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 357 ms 18508 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;
 
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:169:39: warning: unused variable 'noduri' [-Wunused-variable]
  169 |         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 143 ms 4596 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3596 KB Output is correct
2 Correct 67 ms 3548 KB Output is correct
3 Correct 82 ms 11620 KB Output is correct
4 Correct 142 ms 10248 KB Output is correct
5 Correct 145 ms 11744 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4124 KB Output is correct
2 Correct 67 ms 4156 KB Output is correct
3 Correct 57 ms 18508 KB Output is correct
4 Correct 132 ms 18024 KB Output is correct
5 Correct 42 ms 17304 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4972 KB Output is correct
2 Correct 56 ms 4596 KB Output is correct
3 Correct 22 ms 4564 KB Output is correct
4 Correct 15 ms 5076 KB Output is correct
5 Correct 19 ms 4948 KB Output is correct
6 Correct 68 ms 5008 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 8280 KB Output is correct
2 Correct 336 ms 7804 KB Output is correct
3 Correct 234 ms 5388 KB Output is correct
4 Correct 326 ms 7928 KB Output is correct
5 Correct 322 ms 7840 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 11800 KB Output is correct
2 Correct 146 ms 15472 KB Output is correct
3 Correct 210 ms 14468 KB Output is correct
4 Correct 199 ms 13964 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 143 ms 4596 KB Output is correct
3 Correct 65 ms 3596 KB Output is correct
4 Correct 67 ms 3548 KB Output is correct
5 Correct 82 ms 11620 KB Output is correct
6 Correct 142 ms 10248 KB Output is correct
7 Correct 145 ms 11744 KB Output is correct
8 Correct 54 ms 4124 KB Output is correct
9 Correct 67 ms 4156 KB Output is correct
10 Correct 57 ms 18508 KB Output is correct
11 Correct 132 ms 18024 KB Output is correct
12 Correct 42 ms 17304 KB Output is correct
13 Correct 112 ms 4972 KB Output is correct
14 Correct 56 ms 4596 KB Output is correct
15 Correct 22 ms 4564 KB Output is correct
16 Correct 15 ms 5076 KB Output is correct
17 Correct 19 ms 4948 KB Output is correct
18 Correct 68 ms 5008 KB Output is correct
19 Correct 234 ms 8280 KB Output is correct
20 Correct 336 ms 7804 KB Output is correct
21 Correct 234 ms 5388 KB Output is correct
22 Correct 326 ms 7928 KB Output is correct
23 Correct 322 ms 7840 KB Output is correct
24 Correct 357 ms 11800 KB Output is correct
25 Correct 146 ms 15472 KB Output is correct
26 Correct 210 ms 14468 KB Output is correct
27 Correct 199 ms 13964 KB Output is correct
28 Correct 235 ms 7588 KB Output is correct
29 Correct 206 ms 14528 KB Output is correct
30 Correct 128 ms 11844 KB Output is correct
31 Correct 131 ms 17996 KB Output is correct
32 Correct 317 ms 7848 KB Output is correct
33 Correct 210 ms 11888 KB Output is correct
34 Correct 216 ms 13644 KB Output is correct
35 Correct 184 ms 15052 KB Output is correct