oj.uz

Submission #641651

# Submission time Handle Problem Language Result Execution time Memory
641651 2022-09-17T10:49:54 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 412 ms 20804 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 = 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 4948 KB Output is correct
2 Correct 158 ms 6960 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5956 KB Output is correct
2 Correct 80 ms 5956 KB Output is correct
3 Correct 98 ms 14052 KB Output is correct
4 Correct 124 ms 12532 KB Output is correct
5 Correct 147 ms 14132 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6488 KB Output is correct
2 Correct 64 ms 6444 KB Output is correct
3 Correct 46 ms 20804 KB Output is correct
4 Correct 166 ms 20368 KB Output is correct
5 Correct 39 ms 19640 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 7640 KB Output is correct
2 Correct 64 ms 6868 KB Output is correct
3 Correct 25 ms 6912 KB Output is correct
4 Correct 16 ms 7380 KB Output is correct
5 Correct 25 ms 7644 KB Output is correct
6 Correct 77 ms 7336 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 10428 KB Output is correct
2 Correct 409 ms 10292 KB Output is correct
3 Correct 294 ms 7632 KB Output is correct
4 Correct 385 ms 10164 KB Output is correct
5 Correct 412 ms 10308 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 14216 KB Output is correct
2 Correct 184 ms 16860 KB Output is correct
3 Correct 254 ms 16200 KB Output is correct
4 Correct 222 ms 17308 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 158 ms 6960 KB Output is correct
3 Correct 89 ms 5956 KB Output is correct
4 Correct 80 ms 5956 KB Output is correct
5 Correct 98 ms 14052 KB Output is correct
6 Correct 124 ms 12532 KB Output is correct
7 Correct 147 ms 14132 KB Output is correct
8 Correct 63 ms 6488 KB Output is correct
9 Correct 64 ms 6444 KB Output is correct
10 Correct 46 ms 20804 KB Output is correct
11 Correct 166 ms 20368 KB Output is correct
12 Correct 39 ms 19640 KB Output is correct
13 Correct 108 ms 7640 KB Output is correct
14 Correct 64 ms 6868 KB Output is correct
15 Correct 25 ms 6912 KB Output is correct
16 Correct 16 ms 7380 KB Output is correct
17 Correct 25 ms 7644 KB Output is correct
18 Correct 77 ms 7336 KB Output is correct
19 Correct 287 ms 10428 KB Output is correct
20 Correct 409 ms 10292 KB Output is correct
21 Correct 294 ms 7632 KB Output is correct
22 Correct 385 ms 10164 KB Output is correct
23 Correct 412 ms 10308 KB Output is correct
24 Correct 343 ms 14216 KB Output is correct
25 Correct 184 ms 16860 KB Output is correct
26 Correct 254 ms 16200 KB Output is correct
27 Correct 222 ms 17308 KB Output is correct
28 Correct 263 ms 10080 KB Output is correct
29 Correct 232 ms 16248 KB Output is correct
30 Correct 154 ms 14152 KB Output is correct
31 Correct 142 ms 20320 KB Output is correct
32 Correct 388 ms 10204 KB Output is correct
33 Correct 202 ms 15072 KB Output is correct
34 Correct 259 ms 17064 KB Output is correct
35 Correct 225 ms 16756 KB Output is correct