Submission #1159287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159287		arkanefury	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	1098 ms	37940 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 =  1e6+5, M = 210;
int a[N], b[N], pref[N], d[N], c[N], t[N];
int n,m,k,sum=0,x,y, ans, r, cnt, l,inf = -1e18, dist[N], par[N];
string s, str;
vector<int>g[N];
bool f = 0;
void dfs(int v, int p = 0){
    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;
    t[v] = d[v];
}
void sol(int v, int p = 0){
    par[v] = p;
    if(v!=1){
    dist[v] = dist[p]+1;
    c[v] = c[p] + (d[v] == 2);
    }
    for(auto i : g[v]){
        if(i != p)sol(i, v);
    }
}
void jump(int v){
    if(v==1)return;
    sum -= 1 * (d[v] == 2 ? 1 : -1);
    if(d[v]==2)d[v] = 1;
    else d[v] = 2;
    jump(par[v]);
}
void jump1(int v){
    d[v] = t[v];
    if(v==1)return;
    jump1(par[v]);
}
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);
    }
    sum = ans = 0;
    dfs(1);
    sol(1);
    int op = ans;
    FOR(i, 1, m, 1){
        cin >> k;
        int ko = 0;
        ans = 0;
        FOR(j, 1, k, 1){
            cin >> a[j];
            x = a[j];
            if(!pref[x] && g[x].sz==1)pref[x] = 1, ko ++;
            sum = 0;
            jump(x);
            ans += sum;
        }
        FOR(j, 1, k, 1)pref[a[j]]=0, jump1(a[j]);
        if((lp + k - ko) % 2){cout << "-1\n";continue;}
        cout << ans + k + op << '\n';
    }
}
signed main() {
	nikita
	int tt = 1;
	if(!tt)cin >> tt;
	FOR(i, 1, tt, 1) {
		solve();
	}
}

• 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