Submission #1166984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166984		dragst	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	220 ms	24644 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

long long m=1, k=1, p[100005], h[100005], st[400005], lazy[400005], dp[100005], tour[100005];
long long sz[100005], nxt[100005], head[100005], chain[100005], pos[100005], check[100005];
vector<long long> adj[100005], vv;

void dfs(long long x)
{
    sz[x]=1;
    for (auto y: adj[x])
    {
        if (y!=p[x])
        {
            h[y]=h[x]+1;
            p[y]=x;
            dfs(y);
            sz[x]+=sz[y];
            if (sz[y]>sz[nxt[x]]) {nxt[x]=y;};
            dp[x]+=dp[y];
            dp[x]%=2;
            if (dp[x]==0) {dp[x]=2;};
        };
    };
    if (x>1 && adj[x].size()==1) {dp[x]=1;};
}

void hld(long long x)
{
    if (head[m]==0) {head[m]=x;};
    chain[x]=m; tour[k]=x; pos[x]=k; k++;
    if (nxt[x]>0) {hld(nxt[x]);};
    for (auto y: adj[x])
    {
        if (y!=p[x] && y!=nxt[x])
        {
            m++;
            hld(y);
        };
    };
}

void build(long long x, long long l, long long r)
{
    if (l>r) {return;}
    else if (l==r) {st[x]=dp[tour[l]];}
    else
    {
        build(x*2, l, (l+r)/2);
        build(x*2+1, (l+r)/2+1, r);
        st[x]=st[x*2]+st[x*2+1];
    };
}

void fix(long long x, long long l, long long r)
{
    if (lazy[x]%2==1)
    {
        st[x]=3*(r-l+1)-st[x];
        if (l<r) {lazy[x*2]+=lazy[x]; lazy[x*2+1]+=lazy[x];};
        lazy[x]=0;
    };
}

void update(long long x, long long l, long long r, long long pos1, long long pos2)
{
    if (l<=r) {fix(x, l, r);};
    if (l>r || l>pos2 || r<pos1) {return;}
    else if (pos1<=l && r<=pos2) {lazy[x]++; fix(x, l, r);}
    else
    {
        update(x*2, l, (l+r)/2, pos1, pos2);
        update(x*2+1, (l+r)/2+1, r, pos1, pos2);
        st[x]=st[x*2]+st[x*2+1];
    };
}

long long get(long long x, long long l, long long r, long long pos1, long long pos2)
{
    if (l>r || l>pos2 || r<pos1) {return 0LL;}
    else if (pos1<=l && r<=pos2) {fix(x, l, r); return st[x];}
    else {fix(x, l, r); return get(x*2, l, (l+r)/2, pos1, pos2)+get(x*2+1, (l+r)/2+1, r, pos1, pos2);};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	long long n, q, i, u, v;
	cin >> n >> q;
	for (i=1; i<n; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    };
    dfs(1);
    hld(1);
    build(1, 1, n);
    while (q--)
    {
        cin >> i;
        while (i--)
        {
            cin >> u;
            vv.push_back(u);
            check[u]++;
            if (u>1 && adj[u].size()==1 && check[u]==1) {continue;};
            while (u>0)
            {
                update(1, 1, n, pos[head[chain[u]]], pos[u]);
                u=p[head[chain[u]]];
            };
        };
        v=get(1, 1, n, pos[1], pos[1]);
        if (adj[1].size()==1 && check[1]==0 && v==2) {cout << -1 << "\n";}
        else if ((adj[1].size()>1 || check[1]) && v==1) {cout << -1 << "\n";}
        else {cout << get(1, 1, n, 2, n)+vv.size() << "\n";};
        while (!vv.empty())
        {
            u=vv.back();
            vv.pop_back();
            check[u]--;
            if (u>1 && adj[u].size()==1 && check[u]==0) {continue;};
            while (u>0)
            {
                update(1, 1, n, pos[head[chain[u]]], pos[u]);
                u=p[head[chain[u]]];
            };
        };
    };
}

• 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