Submission #1159067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159067		arkanefury	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	57 ms	30532 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 intt __int128
#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];
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){
    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;
}
void sol(int v, int p = 0){
    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 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 = 0;
    dfs(1);
    sol(1);
    FOR(i, 1, m, 1){
        cin >> k;
        if((lp + k)%2){cout << "-1\n";continue;}
        cin >> x;
        if(g[x].sz == 1)cout << ans << '\n';
        else cout << ans + 1 + ( dist[x] - c[x] - c[x] ) << '\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