제출 #1166862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166862		dragst	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1096 ms	17104 KiB

cleaning

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

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

void dfs(long long x)
{
    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]!=0)
    {
        st[x]+=lazy[x]*(r-l+1);
        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, long long k)
{
    if (l<=r) {fix(x, l, r);};
    if (l>r || l>pos2 || r<pos1) {return;}
    else if (pos1<=l && r<=pos2) {lazy[x]+=k; fix(x, l, r);}
    else
    {
        update(x*2, l, (l+r)/2, pos1, pos2, k);
        update(x*2+1, (l+r)/2+1, r, pos1, pos2, k);
        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) {fix(x, l, r);};
    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, check;
	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--)
    {
        check=0;
        cin >> i;
        while (i--)
        {
            cin >> u;
            vv.push_back(u);
            if (u==1) {check++;};
            while (u>0)
            {
                update(1, 1, n, pos[head[chain[u]]], pos[u], 1);
                u=p[head[chain[u]]];
            };
        };
        v=get(1, 1, n, pos[1], pos[1]);
        if (adj[1].size()==1 && check==0 && v%2==0) {cout << -1 << "\n";}
        else if ((adj[1].size()>1 || check) && v%2==1) {cout << -1 << "\n";}
        else {cout << get(1, 1, n, 2, n)+check << "\n";};
        while (!vv.empty())
        {
            u=vv.back();
            while (u>0)
            {
                update(1, 1, n, pos[head[chain[u]]], pos[u], -1);
                u=p[head[chain[u]]];
            };
            vv.pop_back();
        };
    };
}

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