oj.uz

Submission #1098305

# Submission time Handle Problem Language Result Execution time Memory
1098305 2024-10-09T08:53:28 Z Zero_OP Spring cleaning (CEOI20_cleaning) C++14
37 / 100
 1000 ms 20304 KB 
#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

const int MAX = 1e5 + 5;

int n, q, timerHLD, root, parent[MAX], heavy[MAX], sz[MAX], depth[MAX], head[MAX], posHLD[MAX];
vector<int> adj[MAX];
bool original_is_leaf[MAX], is_leaf[MAX];

void predfs(int u, int pre){
    for(int v : adj[u]) if(v != pre){
        depth[v] = depth[u] + 1;
        parent[v] = u;
        predfs(v, u);
        sz[u] += sz[v];
        if(heavy[u] == 0 || sz[heavy[u]] < sz[v]){
            heavy[u] = v;
        }
    }
}

void dfsHLD(int u, int hd){
    head[u] = hd;
    posHLD[u] = ++timerHLD;
    if(heavy[u] != 0){
        dfsHLD(heavy[u], hd);
        for(int v : adj[u]){
            if(v != parent[u] && v != heavy[u]){
                dfsHLD(v, v);
            }
        }
    }
}

struct SegmentTree{
    vector<int> st, lazy;

    SegmentTree(int n) : st(n << 2), lazy(n << 2) {}

    void build(int id, int l, int r){
        st[id] = r - l + 1;
        if(l < r){
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    void flip(int id, int l, int r){
        st[id] = (r - l + 1) - st[id];
        lazy[id] ^= 1;
    }

    void lazyDown(int id, int l, int r, int mid){
        if(lazy[id] > 0){
            flip(id << 1, l, mid);
            flip(id << 1 | 1, mid + 1, r);
            lazy[id] = 0;
        }
    }

    void pull(int id){
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    void update(int id, int l, int r, int u, int v){
        if(u <= l && r <= v){
            flip(id, l, r);
        } else{
            int mid = l + r >> 1;
            lazyDown(id, l, r, mid);
            if(u <= mid) update(id << 1, l, mid, u, v);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v);
            pull(id);
        }
    }

    int getFilled(){
        return st[1];
    }
};

void toggle(int u, SegmentTree& T){
    while(u > 0){
        T.update(1, 1, n, posHLD[head[u]], posHLD[u]);
        u = parent[head[u]];
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    cin >> n >> q;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; ++i){
        if((int)adj[i].size() > 1){
            root = i;
            break;
        }
    }

    predfs(root, -1);
    dfsHLD(root, root);
    SegmentTree T(n);
    T.build(1, 1, n);

    int numLeaves = 0;
    for(int i = 1; i <= n; ++i){
        if((int)adj[i].size() == 1){
            original_is_leaf[i] = true;
            ++numLeaves;
            toggle(i, T);
        }
    }

    copy(original_is_leaf + 1, original_is_leaf + 1 + n, is_leaf + 1);
    int original_numLeaves = numLeaves;

    while(q--){
        vector<int> roll;
        int D;
        cin >> D;
        vector<int> nodes(D);
        for(int i = 0; i < D; ++i){
            cin >> nodes[i];
            if(is_leaf[nodes[i]]){
                is_leaf[nodes[i]] = false;
            } else{
                toggle(nodes[i], T);
                ++numLeaves;
                roll.push_back(nodes[i]);
            }
        }

        if(numLeaves & 1){
            cout << -1 << '\n';
        } else{
            cout << n + D + T.getFilled() - 2 << '\n';
        }

        numLeaves = original_numLeaves;
        for(int u : nodes){
            is_leaf[u] = original_is_leaf[u];
        }

        while(!roll.empty()){
            toggle(roll.back(), T);
            roll.pop_back();
        }
    }
}

Compilation message

cleaning.cpp: In member function 'void SegmentTree::build(int, int, int)':
cleaning.cpp:46:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             int mid = l + r >> 1;
      |                       ~~^~~
cleaning.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
cleaning.cpp:74:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |             int mid = l + r >> 1;
      |                       ~~^~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 153 ms 5244 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4308 KB Output is correct
2 Correct 30 ms 4312 KB Output is correct
3 Correct 49 ms 11980 KB Output is correct
4 Correct 60 ms 10444 KB Output is correct
5 Correct 65 ms 13004 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4820 KB Output is correct
2 Correct 32 ms 4824 KB Output is correct
3 Correct 34 ms 20304 KB Output is correct
4 Correct 116 ms 20176 KB Output is correct
5 Correct 29 ms 18524 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 5464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 10140 KB Output is correct
2 Correct 159 ms 9812 KB Output is correct
3 Correct 114 ms 6480 KB Output is correct
4 Correct 160 ms 9812 KB Output is correct
5 Correct 162 ms 9880 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 13976 KB Output is correct
2 Execution timed out 1027 ms 15440 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 153 ms 5244 KB Output is correct
3 Correct 30 ms 4308 KB Output is correct
4 Correct 30 ms 4312 KB Output is correct
5 Correct 49 ms 11980 KB Output is correct
6 Correct 60 ms 10444 KB Output is correct
7 Correct 65 ms 13004 KB Output is correct
8 Correct 49 ms 4820 KB Output is correct
9 Correct 32 ms 4824 KB Output is correct
10 Correct 34 ms 20304 KB Output is correct
11 Correct 116 ms 20176 KB Output is correct
12 Correct 29 ms 18524 KB Output is correct
13 Execution timed out 1092 ms 5464 KB Time limit exceeded
14 Halted 0 ms 0 KB -