Submission #987099

#	Time	Username	Problem	Language	Result	Execution time	Memory
987099		aykhn	Spring cleaning (CEOI20_cleaning)	C++17	9 / 100	183 ms	19280 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

struct SegTree
{
    int sz;
    vector<int> st, lz;
    void init(int n)
    {
        sz = 1;
        while (sz < n) sz <<= 1;
        st.assign(sz << 1, 0);
        lz.assign(sz << 1, 0);
    }
    void relax(int l, int r, int x)
    {
        if (!lz[x]) return;
        st[x] = r - l - st[x];
        if (l + 1 == r)
        {
            lz[x] = 0;
            return;
        }
        lz[2*x + 1] ^= 1, lz[2*x + 2] ^= 1;
    }
    void make(int l, int r, int x, int lx, int rx)
    {
        if (lx >= rx) return;
        relax(l, r, x);
        if (l >= rx || r <= lx) return;
        if (l >= lx && r <= rx)
        {
            lz[x] ^= 1;
            relax(l, r, x);
            return;
        }
        int mid = (l + r) >> 1;
        make(l, mid, 2*x + 1, lx, rx);
        make(mid, r, 2*x + 2, lx, rx);
        st[x] = st[2*x + 1] + st[2*x + 2];
    }
    int get(int l, int r, int x, int lx, int rx)
    {
        if (lx >= rx) return 0;
        if (l >= rx || r <= lx) return 0;
        relax(l, r, x);
        if (l >= lx && r <= rx) return st[x];
        int mid = (l + r) >> 1;
        return get(l, mid, 2*x + 1, lx, rx) + get(mid, r, 2*x + 2, lx, rx);
    }
};

const int MXN = 1e5 + 5;

int n, q, r, SZ;
vector<int> adj[MXN];
int head[MXN], val[MXN], sz[MXN], dep[MXN], par[MXN];
int in[MXN], out[MXN], tim = -1;
SegTree st;

void _dfs(int a, int p)
{
    sz[a] = 1;
    vector<int> nw;
    for (int v : adj[a])
    {
        if (v == p) continue;
        _dfs(v, a);
        nw.push_back(v);
        sz[a] += sz[v];
    }
    swap(nw, adj[a]);
    int mx = 0;
    for (int i = 0; i < adj[a].size(); i++)
    {
        if (sz[adj[a][i]] > sz[adj[a][mx]]) mx = i;
    }
    if (!adj[a].empty()) swap(adj[a][0], adj[a][mx]);
}
void dfs(int a)
{
    in[a] = ++tim;
    for (int i = 0; i < adj[a].size(); i++)
    {
        if (!i) head[adj[a][i]] = head[a];
        else head[adj[a][i]] = adj[a][i];
        dep[adj[a][i]] = dep[a] + 1;
        par[adj[a][i]] = a;
        dfs(adj[a][i]);
    }
    out[a] = tim;
}
int ans = 0;

void upd(int u, int v)
{
    while (head[u] != head[v])
    {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        if (head[u] == u)
        {
            ans -= val[in[u]];
            val[in[u]] ^= 1;
            ans += val[in[u]];
            u = par[u];
        }
        else
        {
            st.make(0, SZ, 0, in[head[u]] + 1, in[u] + 1);
            u = head[u];
        }
    }
    if (dep[u] < dep[v]) swap(u, v);
    st.make(0, SZ, 0, in[v] + 1, in[u] + 1);
}

int cntleaf = 0;
int add[MXN];

signed main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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 (adj[i].size() >= 2) 
        {
            r = i;
            break;
        }
    }
    st.init(n);
    SZ = st.sz;
    _dfs(r, r);
    head[r] = r;
    dfs(r);
    for (int i = 1; i <= n; i++) 
    {
        cntleaf += adj[i].empty();
        if (adj[i].empty()) upd(r, i);
    }
    for (int i = 1; i <= q; i++)
    {
        set<int> s;
        int d;
        cin >> d;
        for (int j = 1; j <= d; j++)
        {
            int x;
            cin >> x;
            add[x] ^= 1;
            s.insert(x);
        }
        int nw = cntleaf;
        for (int j : s) nw -= adj[j].empty();
        if ((nw + d) & 1)
        {
            for (int j : s) add[j] = 0;
            cout << -1 << '\n';
            continue;
        }
        for (int j : s) 
        {
            if (adj[j].empty() && !add[j]) upd(r, j);
            else if (!adj[j].empty() && add[j]) upd(r, j);
        }
        int all = st.get(0, SZ, 0, 0, n);
        cout << (n - 1 - ans - all) * 2 + ans + all + d << '\n';
        for (int j : s) 
        {
            if (adj[j].empty() && !add[j]) upd(r, j);
            else if (!adj[j].empty() && add[j]) upd(r, j);
        }
        for (int j : s) add[j] = 0;
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'void _dfs(long long int, long long int)':
cleaning.cpp:78:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(long long int)':
cleaning.cpp:87:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30