Submission #1159159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159159		arkanefury	Spring cleaning (CEOI20_cleaning)	C++20	35 / 100	109 ms	87052 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define lb lower_bound
#define F first
#define S second
#define sz size()
#define int long long
#define all(v) v.begin(),v.end()
#define FOR1(x, n) for(int j = x; j <= n; j ++)
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N =  3e6+5, M = 210;
int a[N], b[N], pref[N], d[N], c[N], tin[N], timer = 0, tout[N], t[N];
int n,m,k,sum=0,x,y, ans, r, cnt, l,inf = -1e18, dist[N];
string s, str;
vector<int>g[N];
bool f = 0;
void dfs(int v, int p = 0){
    tin[v] = ++timer;
    for(auto i : g[v]){
        if(i != p)dfs(i, v);
    }
    sum = 0;
    for(auto i : g[v]){
        if(i != p)sum += d[i];
    }
    ans += sum;
    if(sum % 2 || g[v].sz == 1)d[v] = 1;
    else d[v] = 2;
    tout[v] = timer;
}
void sol(int v, int p = 0){
    if(v!=inf){
    dist[v] = dist[p]+1;
    c[v] = c[p] + (d[v] == 2);
    }
    for(auto i : g[v]){
        if(i != p)sol(i, v);
    }
}
void upd(int pos, int v = 1, int tl = 1, int tr = n){
    if(tl==tr){
        t[v] ++;
        return;
    }
    int tm = (tl + tr) >> 1;
    if(pos <= tm)upd(pos, v*2, tl, tm);
    else upd(pos, v*2+1, tm+1, tr);
    t[v] = t[v*2] + t[v*2+1];
}
int get(int l, int r, int v = 1, int tl = 1, int tr = n){
    if(l > tr || tl > r)return 0;
    if(l <= tl && tr <= r)return t[v];
    int tm = (tl + tr) >> 1;
    return get(l, r, v*2, tl, tm) + get(l, r, v*2+1, tm+1, tr);
}
void clear(int v = 1, int tl = 1, int tr = n){
    t[v] = 0;
    int tm = (tl + tr) >> 1;
    if(t[v*2])clear(v*2, tl, tm);
    if(t[v*2+1])clear(v*2+1, tm+1, tr);
    if(tl == tr)return;
}
void solve(){
    cin >> n >> m;
    FOR(i, 2, n, 1){
        cin >> x >> y;
        g[x].pb(y), g[y].pb(x);
    }
    int lp = 0;
    FOR(i, 1, n, 1){
        lp += (g[i].sz==1);
        if(g[i].sz!=1)inf = i;
    }
    sum = 0;
    dfs(inf);
    sol(inf);
    FOR(i, 1, m, 1){
        cin >> k;
        int ko = 0;
        sum = 0;
        vector<pair<int, int>>v;
        FOR(j, 1, k, 1){
            cin >> x;
            v.pb({dist[x], x});
        }
        sort(all(v));
        reverse(all(v));
        FOR(j, 0, k-1, 1){
            x = v[j].S;
            if(g[x].sz == 1 && !pref[x])ko ++, sum ++, pref[x] = 1;
            else{
                sum++;
                int op = get(tin[x], tout[x]);
                sum += (dist[x] - c[x] - c[x]) * (op % 2 ? -1 : 1);
                upd(tin[x]);
            }
        }
        FOR(j, 0, k-1, 1)pref[v[j].S] = 0;
        clear();
        if((k + lp - ko) % 2){cout << "-1\n";continue;}
        cout << ans + sum << '\n';
    }
}
signed main() {
	nikita
	int tt = 1;
	if(!tt)cin >> tt;
	FOR(i, 1, tt, 1) {
		solve();
	}
}

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