Submission #1110408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110408		koukirocks	Spring cleaning (CEOI20_cleaning)	C++17	9 / 100	72 ms	23332 KiB

cleaning

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

void dfs(int v,int p,vvector<int> &G,vector<int> &cnt,vector<pii> &dfn,int &tm,vector<int> &dep) {
    dfn[v].F=tm++;
    cnt[v]=(G[v].size()<=1);
    for (int i:G[v]) {
        if (i==p) continue;
        dep[i]=dep[v]+1;
        dfs(i,v,G,cnt,dfn,tm,dep);
        cnt[v]^=cnt[i];
    }
    // cout<<v<<" "<<cnt[v]<<" v cnt\n";
    dfn[v].S=tm++;
}

int dfs2(int v,int p,vvector<int> &G,vector<int> &cnt,int &ans) {
    ans+=cnt[v];
    cnt[v]+=cnt[p];
    int ttl=(G[v].size()==1);
    for (int i:G[v]) {
        if (i==p) continue;
        ttl+=dfs2(i,v,G,cnt,ans);
    }
    return ttl;
}

struct BIT {
    int n;
    vector<int> a;
    BIT(int n):n(n) {
        a.resize(n+1);
    }
    void update(int x,int val) {
        while (x<=n) {
            a[x]+=val;
            x+=(-x&x);
        }
    }
    int query(int x) {
        int ans=0;
        while (x) {
            ans+=a[x];
            x-=(-x&x);
        }
        return ans;
    }
};

int main() {
    speed;
    int n,q;
    cin>>n>>q;
    vvector<int> G(n+1);
    for (int i=0;i<n-1;i++) {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int rt=0;
    for (int i=1;i<=n;i++) {
        if (G[i].size()>1) {
            rt=i;
            break;
        }
    }
    vector<int> cnt(n+1),dep(n+1);
    vector<pii> dfn(n+1);
    int tm=1;
    dfs(rt,0,G,cnt,dfn,tm,dep);
    cnt[rt]=0;
    int ans=0;
    int tlv = dfs2(rt,0,G,cnt,ans);
    BIT b(tm-1);
    // cout<<rt<<" "<<ans<<" rt ans\n";
    while (q--) {
        int d;
        cin>>d;
        map<int,int> app;
        for (int i=0;i<d;i++) {
            int x;
            cin>>x;
            app[x]++;
        }
        vector<int> ttl;
        for (auto [i,x]:app) {
            if (x&1) ttl.push_back(i);
        }
        sort(all(ttl),[&](int a,int b) {
            return dep[a]>dep[b];
        });
        ll dta=0;
        for (int v:ttl) {
            int rev = b.query(dfn[v].S)-b.query(dfn[v].F-1);
            // cout<<v<<" "<<rev<<" v rev\n";
            if (rev&1) dta+=2*cnt[v]-dep[v];
            else dta+=dep[v]-2*cnt[v];
            b.update(dfn[v].F,1);
            if (G[v].size()==1) d--;
        }
        for (int v:ttl) b.update(dfn[v].F,-1);
        // cout<<2*(n-1)<<" "<<ans<<" "<<dta<<" "<<d<<" 2*(n-1) ans dta d\n";
        if ((tlv+d)&1) {
            cout<<"-1\n";
            continue;
        }
        int qans=2*(n-1)-(ans+dta)+d;
        cout<<qans<<"\n";
    }
    return 0;
}

/*
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
*/

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