oj.uz

Submission #1081987

# Submission time Handle Problem Language Result Execution time Memory
1081987 2024-08-30T14:00:09 Z cpptowin Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 244 ms 39760 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
struct SegmentTree
{
    vector<int> st, lazy;
    int n;
    stack<pair<int,int>> event;
    /// real n
    SegmentTree(int _n = 0) : n(_n)
    {
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10);
    }
    void resize(int _n)
    {
        n = _n;
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10);
    }
    void down(int id, int l, int r)
    {
        if (lazy[id] == 0)
            return;
        int mid = l + r >> 1;
        st[id << 1] = (mid - l + 1) - st[id << 1];
        lazy[id << 1] ^= 1;
        st[id << 1 | 1] = (r - mid) - st[id << 1 | 1];
        lazy[id << 1 | 1] ^= 1;
        lazy[id] = 0;
    }
    void build(int id, int l, int r)
    {
        if (l == r)
        {
            st[id] = r - l + 1;
            return;
        }
        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 update(int id, int l, int r, int u, int v)
    {
        if (u > r || l > v)
            return;
        if (u <= l && r <= v)
        {
            st[id] = (r - l + 1) - st[id];
            lazy[id] ^= 1;
            return;
        }
        down(id, l, r);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v);
        update(id << 1 | 1, mid + 1, r, u, v);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    int get(int id, int l, int r, int u, int v)
    {
        if (l > v || u > r)
            return 0;
        if (u <= l && r <= v)
            return st[id];
        down(id, l, r);
        int mid = (l + r) >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
    void update(int l, int r)
    {
        event.push({l,r});
        update(1, 1, n, l, r);
    }
    void rollback(int i)
    {
        while(ss(event) > i) 
        {
            auto [l,r] = event.top();
            update(1,1,n,l,r);
            event.pop();
        }
    }
} st(maxn);
vi ke[maxn];
int n, q;
int par[maxn][20];
int h[maxn];
int head[maxn], ind[maxn], pos[maxn], sz[maxn];
int cnt, chaincnt;
void dfs(int u)
{
    sz[u] = 1;
    for (int v : ke[u])
    {
        if (v == par[u][0])
            continue;
        h[v] = h[u] + 1;
        par[v][0] = u;
        fo(i, 1, 19) par[v][i] = par[par[v][i - 1]][i - 1];
        dfs(v);
        sz[u] += sz[v];
    }
}
void hld(int u)
{
    if (head[chaincnt] == 0)
        head[chaincnt] = u;
    ind[u] = chaincnt;
    pos[u] = ++cnt;
    int maxx = 0, sc = -1;
    for (int v : ke[u])
    {
        if (v == par[u][0])
            continue;
        if (sz[v] > maxx)
        {
            maxx = sz[v], sc = v;
        }
    }
    if (sc != -1)
        hld(sc);
    for (int v : ke[u])
        if (v != sc && v != par[u][0])
        {
            ++chaincnt;
            hld(v);
        }
}
int lca(int u, int v)
{
    if (h[u] < h[v])
        swap(u, v);
    int del = h[u] - h[v];
    fod(i, 19, 0) if (bit(del, i)) u = par[u][i];
    if (u == v)
        return u;
    fod(i, 19, 0) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}
void change(int u, int v)
{
    int uchain, vchain = ind[v];
    while (1)
    {
        uchain = ind[u];
        if (uchain == vchain)
        {
            st.update(pos[v], pos[u]);
            return;
        }
        st.update(pos[head[uchain]], pos[u]);
        u = par[head[uchain]][0];
    }
}
bool ok[maxn];
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    st.resize(n);
    st.build(1, 1, n);
    fo(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    int root;
    fo(i, 1, n) if (ss(ke[i]) > 1)
    {
        root = i;
        dfs(root);
        hld(root);
        break;
    }
    int leaves = 0;
    fo(i, 1, n) if (ss(ke[i]) == 1)
    {
        ok[i] = 1;
        leaves++;
        change(i, root);
    }
    while (q--)
    {
        int m;
        cin >> m;
        vi v(m);
        int l1 = leaves;
        int timer = ss(st.event);
        for (int &x : v)
        {
            cin >> x;
            if (ok[x]) ok[x] = 0;
            else
            {
                leaves++;
                change(x, root);
            }
        }
        if (leaves % 2 == 1)cout << -1;
        else cout << n + m + st.st[1] - 2;
        en;
        leaves = l1;
        st.rollback(timer);
        for(int x : v) ok[x] = (ss(ke[x]) == 1);
    }
}

Compilation message

cleaning.cpp: In member function 'void SegmentTree::down(long long int, long long int, long long int)':
cleaning.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l + r >> 1;
      |                   ~~^~~
cleaning.cpp: In member function 'void SegmentTree::build(long long int, long long int, long long int)':
cleaning.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = l + r >> 1;
      |                   ~~^~~
cleaning.cpp: At global scope:
cleaning.cpp:217:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  217 | main()
      | ^~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:222:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  222 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:223:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:266:23: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  266 |                 change(x, root);
      |                 ~~~~~~^~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9048 KB Output is correct
2 Correct 82 ms 15148 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13200 KB Output is correct
2 Correct 42 ms 13404 KB Output is correct
3 Correct 78 ms 36684 KB Output is correct
4 Correct 90 ms 30916 KB Output is correct
5 Correct 106 ms 38852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12892 KB Output is correct
2 Correct 33 ms 13144 KB Output is correct
3 Correct 48 ms 39760 KB Output is correct
4 Correct 96 ms 39480 KB Output is correct
5 Correct 44 ms 36948 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 15440 KB Output is correct
2 Correct 39 ms 14936 KB Output is correct
3 Correct 23 ms 14684 KB Output is correct
4 Correct 19 ms 14680 KB Output is correct
5 Correct 17 ms 14940 KB Output is correct
6 Correct 45 ms 15004 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 30564 KB Output is correct
2 Correct 244 ms 30604 KB Output is correct
3 Correct 146 ms 20048 KB Output is correct
4 Correct 220 ms 30548 KB Output is correct
5 Correct 217 ms 30548 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 38708 KB Output is correct
2 Correct 131 ms 39504 KB Output is correct
3 Correct 151 ms 38040 KB Output is correct
4 Correct 139 ms 37460 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9048 KB Output is correct
2 Correct 82 ms 15148 KB Output is correct
3 Correct 41 ms 13200 KB Output is correct
4 Correct 42 ms 13404 KB Output is correct
5 Correct 78 ms 36684 KB Output is correct
6 Correct 90 ms 30916 KB Output is correct
7 Correct 106 ms 38852 KB Output is correct
8 Correct 35 ms 12892 KB Output is correct
9 Correct 33 ms 13144 KB Output is correct
10 Correct 48 ms 39760 KB Output is correct
11 Correct 96 ms 39480 KB Output is correct
12 Correct 44 ms 36948 KB Output is correct
13 Correct 60 ms 15440 KB Output is correct
14 Correct 39 ms 14936 KB Output is correct
15 Correct 23 ms 14684 KB Output is correct
16 Correct 19 ms 14680 KB Output is correct
17 Correct 17 ms 14940 KB Output is correct
18 Correct 45 ms 15004 KB Output is correct
19 Correct 165 ms 30564 KB Output is correct
20 Correct 244 ms 30604 KB Output is correct
21 Correct 146 ms 20048 KB Output is correct
22 Correct 220 ms 30548 KB Output is correct
23 Correct 217 ms 30548 KB Output is correct
24 Correct 214 ms 38708 KB Output is correct
25 Correct 131 ms 39504 KB Output is correct
26 Correct 151 ms 38040 KB Output is correct
27 Correct 139 ms 37460 KB Output is correct
28 Correct 152 ms 26824 KB Output is correct
29 Correct 157 ms 39252 KB Output is correct
30 Correct 110 ms 38852 KB Output is correct
31 Correct 98 ms 39508 KB Output is correct
32 Correct 218 ms 30628 KB Output is correct
33 Correct 127 ms 32080 KB Output is correct
34 Correct 148 ms 37776 KB Output is correct
35 Correct 148 ms 37716 KB Output is correct