Submission #1043679

#TimeUsernameProblemLanguageResultExecution timeMemory
1043679beaconmcSpring cleaning (CEOI20_cleaning)C++14
9 / 100
1073 ms15560 KiB
#include <bits/stdc++.h> typedef long long ll; #define FOR(i,x,y) for(ll i=x; i<y; i++) #define FORNEG(i,x,y) for(ll i=x; i>y; i--) using namespace std; vector<ll> edges[200005]; ll realans = 0; ll vals[200005]; ll origvals[200005]; ll par[200005]; int dp(ll a, ll p){ par[a] = p; ll ans = 0; if (edges[a].size() <= 1) ans = 1; for (auto&i : edges[a]){ if (i != p) ans += dp(i, a); } if (p!=-1) realans += 1 + (ans+1)%2; if (p != -1) vals[a] = 1 + (ans+1)%2; origvals[a] = 1 + (ans+1)%2; return 1 + (ans+1)%2; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll n,q; cin >> n >> q; FOR(i,0,n-1){ ll a,b; cin >> a >> b; edges[a].push_back(b); edges[b].push_back(a); } ll root = -1; ll cnt = 0; FOR(j,1,n+1){ if (edges[j].size() != 1){ root = j; }else{ cnt++; } } dp(root, -1); ll ans = 0; FOR(i,1,n+1) ans += vals[i]; FOR(i,0,q){ ll d; cin >> d; ll cur = n+1; ll curans = 0; set<ll> used; ll newleaves=0; FOR(k,0,d){ ll temp; cin >> temp; if (edges[temp].size() != 1){ newleaves++; curans+= 1; ll idk = temp; while (idk != root){ used.insert(idk); if (vals[idk]==1) curans += 1, vals[idk]=2; else curans -= 1, vals[idk] = 1; idk = par[idk]; } }else{ curans += 1; } edges[temp].push_back(cur++); } for (auto&k : used){ vals[k] = origvals[k]; } if ((cnt+newleaves)%2==1) cout << -1 << "\n"; else{ cout << ans+curans << "\n"; } FOR(i,1,n+1){ while (edges[i].size() && edges[i][edges[i].size()-1]>n){ edges[i].pop_back(); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...