Submission #485799

#	Time	Username	Problem	Language	Result	Execution time	Memory
485799		radal	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	238 ms	34488 KiB

cleaning

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<long double,long double> pld;
const long long int N = 2e5+10,mod = 1e9+7,inf = 1e9,sq = 500,maxm = 1e5+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
vector<int> adj[N];
bool leaf[N],vis[N];
int ans,par[N][20],h[N],tin[N],T;
int cnt[N][2],L[N],R[N];
void dfs(int v,int p){
    par[v][0] = p;
    tin[v] = T;
    T++;
    for (int u : adj[v]){
        if (u == p) continue;
        h[u] = h[v]+1;
        dfs(u,v);
        if (leaf[u]){
            ans++;
            leaf[v] = !leaf[v];
        }
        else ans += 2;
    }
    if(adj[v].size() == 1) leaf[v] = 1;
}
inline int lca(int u,int v){
    if (h[u] > h[v]) swap(u,v);
    repr(i,19,0){
        if (h[v]-h[u] >= (1 << i))
            v = par[v][i];
    }
    if (u == v) return v;
    repr(i,19,0){
        if (par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
void dfs2(int v){
    for (int u : adj[v]){
        if(u == par[v][0]) continue;
        cnt[u][0] = cnt[v][0];
        cnt[u][1] = cnt[v][1];
        cnt[u][leaf[u]]++;
        dfs2(u);
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,q;
    cin >> n >> q;
    int r = -1;
    rep(i,1,n){
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        if (adj[u].size() == 2) r = u;
        else if (adj[v].size() == 2) r = v;
    }
    dfs(r,-1);
    dfs2(r);
    rep(j,1,19){
        rep(i,1,n+1){
            if (h[i] < (1 << j)) continue;
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    while (q--){
        int t,out;
        cin >> t;
        out = ans+t;
        vector<int> ve;
        vector<pll> ve2;
        ve.reserve(t);
        rep(i,0,t){
            int p;
            cin >> p;
            ve.pb(p);
            if (adj[p].size() > 1 || vis[p])
                ve2.pb({tin[p],p});
            else vis[p] = 1;
        }
        rep(i,0,t) vis[ve[i]] = 0;
        sort(ve2.begin(),ve2.end());
        set<pll> st;
        set<int> st2;
        int sz = ve2.size();
        if (leaf[r] != (sz&1)){
            cout << -1 << endl;
            continue;
        }
        if (!sz){
            cout << out << endl;
            continue;
        }
        rep(i,0,sz-1){
            int w = lca(ve2[i].Y,ve2[i+1].Y);
            st.insert({-h[w],i});
            st2.insert(i);
            L[i] = i-1;
            R[i] = i+1;
        }
        R[sz-1] = sz;
        st2.insert(sz-1);
        while (!st.empty()){
            pll p = *(st.begin());
            st.erase(st.begin());
            int v = ve2[p.Y].Y;
            int u = ve2[R[p.Y]].Y;
            st2.erase(R[p.Y]);
            st2.erase(p.Y);
            int w = lca(u,v);
            out = out+(cnt[v][1]+cnt[u][1]-2*cnt[w][1])-(cnt[v][0]+cnt[u][0]-2*cnt[w][0]);
            if (L[p.Y] != -1){
                R[L[p.Y]] = R[R[p.Y]];
                st.erase({-h[lca(v,ve2[L[p.Y]].Y)],L[p.Y]});
            }
            if (R[R[p.Y]] < sz){
                L[R[R[p.Y]]] = L[p.Y];
                st.erase({-h[lca(u,ve2[R[R[p.Y]]].Y)],R[p.Y]});
            }
            if (L[p.Y] != -1 && R[R[p.Y]] < sz)
                st.insert({-h[lca(ve2[L[p.Y]].Y,ve2[R[R[p.Y]]].Y)],L[p.Y]});
        }
        if (!st2.empty()){
            int ind = *(st2.begin());
            int u = ve2[ind].Y;
            out = out + cnt[u][1]-cnt[u][0];
        }
        rep(i,0,sz-1) L[i] = R[i] = 0;
        cout << out << endl;
    }
}

• 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