oj.uz

Submission #641677

# Submission time Handle Problem Language Result Execution time Memory
641677 2022-09-17T12:17:51 Z Vladth11 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 355 ms 21132 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 = 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: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 2 ms 4948 KB Output is correct
2 Correct 136 ms 7288 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6008 KB Output is correct
2 Correct 73 ms 5996 KB Output is correct
3 Correct 84 ms 14124 KB Output is correct
4 Correct 112 ms 12860 KB Output is correct
5 Correct 133 ms 14448 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6588 KB Output is correct
2 Correct 57 ms 6652 KB Output is correct
3 Correct 47 ms 21132 KB Output is correct
4 Correct 124 ms 20584 KB Output is correct
5 Correct 41 ms 19916 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 7512 KB Output is correct
2 Correct 56 ms 7076 KB Output is correct
3 Correct 24 ms 6992 KB Output is correct
4 Correct 16 ms 7584 KB Output is correct
5 Correct 21 ms 7468 KB Output is correct
6 Correct 63 ms 7544 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 10692 KB Output is correct
2 Correct 330 ms 10436 KB Output is correct
3 Correct 231 ms 7856 KB Output is correct
4 Correct 333 ms 10460 KB Output is correct
5 Correct 315 ms 10400 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 14460 KB Output is correct
2 Correct 167 ms 18028 KB Output is correct
3 Correct 219 ms 17192 KB Output is correct
4 Correct 211 ms 16760 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 136 ms 7288 KB Output is correct
3 Correct 66 ms 6008 KB Output is correct
4 Correct 73 ms 5996 KB Output is correct
5 Correct 84 ms 14124 KB Output is correct
6 Correct 112 ms 12860 KB Output is correct
7 Correct 133 ms 14448 KB Output is correct
8 Correct 55 ms 6588 KB Output is correct
9 Correct 57 ms 6652 KB Output is correct
10 Correct 47 ms 21132 KB Output is correct
11 Correct 124 ms 20584 KB Output is correct
12 Correct 41 ms 19916 KB Output is correct
13 Correct 116 ms 7512 KB Output is correct
14 Correct 56 ms 7076 KB Output is correct
15 Correct 24 ms 6992 KB Output is correct
16 Correct 16 ms 7584 KB Output is correct
17 Correct 21 ms 7468 KB Output is correct
18 Correct 63 ms 7544 KB Output is correct
19 Correct 243 ms 10692 KB Output is correct
20 Correct 330 ms 10436 KB Output is correct
21 Correct 231 ms 7856 KB Output is correct
22 Correct 333 ms 10460 KB Output is correct
23 Correct 315 ms 10400 KB Output is correct
24 Correct 355 ms 14460 KB Output is correct
25 Correct 167 ms 18028 KB Output is correct
26 Correct 219 ms 17192 KB Output is correct
27 Correct 211 ms 16760 KB Output is correct
28 Correct 230 ms 10208 KB Output is correct
29 Correct 196 ms 17144 KB Output is correct
30 Correct 130 ms 14356 KB Output is correct
31 Correct 128 ms 20492 KB Output is correct
32 Correct 319 ms 10308 KB Output is correct
33 Correct 213 ms 14440 KB Output is correct
34 Correct 217 ms 16236 KB Output is correct
35 Correct 186 ms 17564 KB Output is correct