Submission #1167005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167005		hahahoang132	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	318 ms	22332 KiB

cleaning

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 1e5 + 5;
const ll mod = 998244353;
const ll inf = LLONG_MAX/3;
#define bit(x,y) ((x >> y) & 1LL)
vector<ll> a[N];
ll id[N],ide[N],sz[N],bc[N],p[N],ch[N],uv[N],sum = 0,rt;
ll ti = 0;
void build(ll x, ll px)
{
    p[x] = px;
    sz[x] = 1;
    for(auto y : a[x])
    {
        if(y == px) continue;
        build(y,x);
        sz[x] += sz[y];
        if(sz[bc[x]] < sz[y]) bc[x] = y;
    }
}
void build2(ll x, ll px)
{
    id[x] = ide[x] = ++ti;
    if(bc[x])
    {
        build2(bc[x],x);
        ide[x] = ide[bc[x]];
    }
    for(auto y : a[x])
    {
        if(y == px || y == bc[x]) continue;
        build2(y,x);
        ide[x] = ide[y];
    }
}
struct segtree
{
    ll n;
    ll b[N * 4];
    ll lz[N * 4];
    void build(ll n)
    {
        this->n = n;
    }
    void push(ll x, ll l, ll mid, ll r)
    {
        if(lz[x] == 0) return;
        ll x1 = x * 2 + 1;
        ll x2 = x1 + 1;
        ll sz1 = mid - l + 1;
        ll sz2 = r - mid;
        b[x1] = sz1 - b[x1];
        lz[x1] ^= 1;
        b[x2] = sz2 - b[x2];
        lz[x2] ^= 1;
        lz[x] = 0;
    }
    void udt(ll l, ll r)
    {
        udt(0,1,n,l,r);
    }
    void udt(ll x, ll l, ll r, ll s, ll e)
    {
        if(s <= l && r <= e)
        {
            ll sz = r - l + 1;
            b[x] = sz - b[x];
            lz[x] ^= 1;
            return;
        }
        if(r < s || e < l) return;
        ll mid = (l + r) / 2;
        push(x,l,mid,r);
        udt(x * 2 + 1,l,mid,s,e);
        udt(x * 2 + 2,mid + 1,r,s,e);
        b[x] = b[x * 2 + 1] + b[x * 2 + 2];
    }
    ll get(ll l, ll r)
    {
        l = max(2LL,l);
        if(l > r) return 0;
        return get(0,1,n,l,r);
    }
    ll get(ll x, ll l, ll r, ll s, ll e)
    {
        if(s <= l && r <= e) return b[x];
        if(r < s || e < l) return 0;
        ll mid = (l + r) / 2;
        push(x,l,mid,r);
        return get(x * 2 + 1,l,mid,s,e) + get(x * 2 + 2,mid + 1,r,s,e);
    }
    ll rget()
    {
        return rget(0,1,n);
    }
    ll rget(ll x, ll l, ll r)
    {
        if(l == r) return b[x];
        ll mid = (l + r) / 2;
        push(x,l,mid,r);
        return rget(x * 2 + 1,l,mid);
    }
};
segtree f;
void buildval(ll x, ll px)
{
    uv[x] = 0;
    for(auto y : a[x])
    {
        if(y == px) continue;
        buildval(y,x);
        uv[x] += uv[y];
    }
    if(uv[x] == 0)
    {
        uv[x] = 1;
    }else
    {
        if(uv[x] % 2 == 0) uv[x] = 2;
        else uv[x] = 1;
    }
    if(x != rt) sum += uv[x];
    if(uv[x] == 1) f.udt(id[x],id[x]);
}
void buildchain(ll x, ll chx)
{
    ch[x] = chx;
    if(bc[x]) buildchain(bc[x],chx);
}
ll get(ll x)
{
    ll ans = 0;
    while(x != 0)
    {
        ll c1 = f.get(id[ch[x]],id[x]);
        ll c2 = (id[x] - id[ch[x]] + (ch[x] != rt)) - c1;
        ans += c1 - c2;
        f.udt(id[ch[x]],id[x]);
        x = p[ch[x]];
    }
    return ans;
}
void cle(ll x)
{
    while(x != 0)
    {
        f.udt(id[ch[x]],id[x]);
        x = p[ch[x]];
    }
}
ll isleaf[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,q;
    cin >> n >> q;
    ll i,j;
    for(i = 1;i < n;i++)
    {
        ll u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(i = 1;i <= n;i++)
    {
        if(a[i].size() >= 2) rt = i;
        else isleaf[i] = 1;
    }
    f.build(n);
    build(rt,0);
    build2(rt,0);
    buildval(rt,0);
    for(i = 1;i <= n;i++)
    {
        if(bc[p[i]] == i) continue;
        buildchain(i,i);
    }
    while(q--)
    {
        ll k;
        cin >> k;
        ll ans = sum;
        vector<pair<ll,ll>> haha;
        for(i = 1;i <= k;i++)
        {
            ll x;
            cin >> x;
            if(isleaf[x])
            {
                isleaf[x] = 0;
                ans++;
                haha.push_back({x,1});
            }else
            {
                ans += get(x) + 1;
                haha.push_back({x,0});
            }
        }
        if(f.rget() == 0) cout << ans << "\n";
        else cout << -1 << "\n";
        while(haha.size() > 0)
        {
            ll x = haha.back().first;
            ll tt = haha.back().second;
            haha.pop_back();
            if(tt == 0) cle(x);
            else isleaf[x] = 1;
        }
    }
}

• 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