oj.uz

Submission #641614

# Submission time Handle Problem Language Result Execution time Memory
641614 2022-09-17T09:57:11 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 399 ms 21928 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++;
    }
    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: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 3 ms 4996 KB Output is correct
2 Correct 159 ms 6984 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 5960 KB Output is correct
2 Correct 97 ms 6312 KB Output is correct
3 Correct 94 ms 14788 KB Output is correct
4 Correct 126 ms 13596 KB Output is correct
5 Correct 147 ms 15508 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6428 KB Output is correct
2 Correct 70 ms 6472 KB Output is correct
3 Correct 47 ms 20868 KB Output is correct
4 Correct 138 ms 20288 KB Output is correct
5 Correct 41 ms 19712 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 7328 KB Output is correct
2 Correct 71 ms 7332 KB Output is correct
3 Correct 25 ms 7080 KB Output is correct
4 Correct 17 ms 7604 KB Output is correct
5 Correct 24 ms 7472 KB Output is correct
6 Correct 74 ms 7892 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 10580 KB Output is correct
2 Correct 386 ms 11520 KB Output is correct
3 Correct 285 ms 8628 KB Output is correct
4 Correct 386 ms 11476 KB Output is correct
5 Correct 390 ms 11540 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 14156 KB Output is correct
2 Correct 174 ms 17748 KB Output is correct
3 Correct 241 ms 18688 KB Output is correct
4 Correct 231 ms 18312 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4996 KB Output is correct
2 Correct 159 ms 6984 KB Output is correct
3 Correct 106 ms 5960 KB Output is correct
4 Correct 97 ms 6312 KB Output is correct
5 Correct 94 ms 14788 KB Output is correct
6 Correct 126 ms 13596 KB Output is correct
7 Correct 147 ms 15508 KB Output is correct
8 Correct 81 ms 6428 KB Output is correct
9 Correct 70 ms 6472 KB Output is correct
10 Correct 47 ms 20868 KB Output is correct
11 Correct 138 ms 20288 KB Output is correct
12 Correct 41 ms 19712 KB Output is correct
13 Correct 135 ms 7328 KB Output is correct
14 Correct 71 ms 7332 KB Output is correct
15 Correct 25 ms 7080 KB Output is correct
16 Correct 17 ms 7604 KB Output is correct
17 Correct 24 ms 7472 KB Output is correct
18 Correct 74 ms 7892 KB Output is correct
19 Correct 286 ms 10580 KB Output is correct
20 Correct 386 ms 11520 KB Output is correct
21 Correct 285 ms 8628 KB Output is correct
22 Correct 386 ms 11476 KB Output is correct
23 Correct 390 ms 11540 KB Output is correct
24 Correct 362 ms 14156 KB Output is correct
25 Correct 174 ms 17748 KB Output is correct
26 Correct 241 ms 18688 KB Output is correct
27 Correct 231 ms 18312 KB Output is correct
28 Correct 260 ms 11220 KB Output is correct
29 Correct 233 ms 18612 KB Output is correct
30 Correct 147 ms 15520 KB Output is correct
31 Correct 152 ms 21928 KB Output is correct
32 Correct 399 ms 11456 KB Output is correct
33 Correct 225 ms 15740 KB Output is correct
34 Correct 264 ms 17816 KB Output is correct
35 Correct 241 ms 19252 KB Output is correct