Submission #1166491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166491		cpismylifeOwO	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	215 ms	44872 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

int n, q;
vector<int> graph[MaxN];

void Inp()
{
    cin >> n >> q;
    for (int x = 1; x < n; x++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

int root;
int Pre[MaxN];
int h[MaxN];
int par[MaxN];
int nxt[MaxN];
int sz[MaxN];

void PreDFS(int u, int p)
{
    Pre[u] = ((int)graph[u].size() == 1);
    nxt[u] = -1;
    sz[u] = 1;
    for (int x : graph[u])
    {
        if (x != p)
        {
            h[x] = h[u] + 1;
            par[x] = u;
            PreDFS(x, u);
            Pre[u] ^= Pre[x];
            sz[u] += sz[x];
            if (nxt[u] == -1 || sz[nxt[u]] < sz[x])
            {
                nxt[u] = x;
            }
        }
    }
}

int CurChain, CurPos;
int ChainHead[MaxN];
int ChainID[MaxN];
int Pos[MaxN];
int Arr[MaxN];

void HLD(int u, int p)
{
    if (ChainHead[CurChain] == 0)
    {
        ChainHead[CurChain] = u;
    }
    ChainID[u] = CurChain;
    Pos[u] = CurPos;
    Arr[CurPos] = u;
    CurPos++;
    if (nxt[u] != -1)
    {
        HLD(nxt[u], u);
    }
    for (int x : graph[u])
    {
        if (x != p && x != nxt[u])
        {
            CurChain++;
            HLD(x, u);
        }
    }
}

struct Node
{
    int cnt0, cnt1, sum;

    Node() = default;

    Node(int _cnt0, int _cnt1, int _sum)
    {
        cnt0 = _cnt0;
        cnt1 = _cnt1;
        sum = _sum;
    }

    Node& operator = (const Node& other)
    {
        this->cnt0 = other.cnt0;
        this->cnt1 = other.cnt1;
        this->sum = other.sum;
        return *this;
    }

    Node operator * (const Node& other) const
    {
        Node res;
        res.cnt0 = this->cnt0 + other.cnt0;
        res.cnt1 = this->cnt1 + other.cnt1;
        res.sum = this->sum + other.sum;
        return res;
    }
};

Node SegTree[4 * MaxN];
int Lazy[4 * MaxN];

void Fix(int id, int l, int r)
{
    if (Lazy[id] == 0)
    {
        return;
    }
    swap(SegTree[id].cnt0, SegTree[id].cnt1);
    SegTree[id].sum = SegTree[id].cnt1 + SegTree[id].cnt0 * 2;
    if (l != r)
    {
        Lazy[id << 1] ^= Lazy[id];
        Lazy[id << 1 | 1] ^= Lazy[id];
    }
    Lazy[id] = 0;
}

void Build(int id, int l, int r)
{
    Lazy[id] = 0;
    if (l == r)
    {
        SegTree[id] = Node((Pre[Arr[l]] == 0), (Pre[Arr[r]] == 1), 2 * (Pre[Arr[l]] == 0) + (Pre[Arr[r]] == 1));
        return;
    }
    int mid = (l + r) >> 1;
    Build(id << 1, l, mid);
    Build(id << 1 | 1, mid + 1, r);
    SegTree[id] = SegTree[id << 1] * SegTree[id << 1 | 1];
}

void Update(int id, int l, int r, int i, int j)
{
    Fix(id, l, r);
    if (j < l || r < i)
    {
        return;
    }
    if (i <= l && r <= j)
    {
        Lazy[id] ^= 1;
        Fix(id, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    Update(id << 1, l, mid, i, j);
    Update(id << 1 | 1, mid + 1, r, i, j);
    SegTree[id] = SegTree[id << 1] * SegTree[id << 1 | 1];
}

Node Get(int id, int l, int r, int i, int j)
{
    Fix(id, l, r);
    if (j < l || r < i)
    {
        return Node(0, 0, 0);
    }
    if (i <= l && r <= j)
    {
        return SegTree[id];
    }
    int mid = (l + r) >> 1;
    return Get(id << 1, l, mid, i, j) * Get(id << 1 | 1, mid + 1, r, i, j);
}

void UpdatePath(int u)
{
    while (ChainID[u] != ChainID[root])
    {
        Update(1, 1, n, Pos[ChainHead[ChainID[u]]], Pos[u]);
        u = par[ChainHead[ChainID[u]]];
    }
    Update(1, 1, n, Pos[root], Pos[u]);
}

bool mark[MaxN];

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        if ((int)graph[x].size() > 1)
        {
            root = x;
            break;
        }
    }
    PreDFS(root, -1);
    CurChain = CurPos = 1;
    HLD(root, -1);
    Build(1, 1, n);
    //cout << Get(1, 1, n, 1, n).sum - Get(1, 1, n, Pos[root], Pos[root]).sum << " ";
    for (int x = 1; x <= q; x++)
    {
        set<int> s;
        int d;
        cin >> d;
        for (int y = 1; y <= d; y++)
        {
            int u;
            cin >> u;
            mark[u] ^= 1;
            s.insert(u);
        }
        for (int x : s)
        {
            if ((int)graph[x].size() == 1)
            {
                if (mark[x] == 0)
                {
                    UpdatePath(x);
                }
            }
            else
            {
                if (mark[x] == 1)
                {
                    UpdatePath(x);
                }
            }
        }
        int res = 0;
        if (Get(1, 1, n, Pos[root], Pos[root]).cnt0)
        {
            res = Get(1, 1, n, 1, n).sum - Get(1, 1, n, Pos[root], Pos[root]).sum + d;
        }
        else
        {
            res = -1;
        }
        for (int x : s)
        {
            if ((int)graph[x].size() == 1)
            {
                if (mark[x] == 0)
                {
                    UpdatePath(x);
                }
            }
            else
            {
                if (mark[x] == 1)
                {
                    UpdatePath(x);
                }
            }
            mark[x] = 0;
        }
        cout << res << "\n";
    }
}

int main()
{
    //freopen("A.INP", "r", stdin);
    //freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int w = 1; w <= test; w++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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