Submission #976203

#TimeUsernameProblemLanguageResultExecution timeMemory
976203efedmrlrSpring cleaning (CEOI20_cleaning)C++17
34 / 100
1093 ms16464 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,popcnt") #include <bits/stdc++.h> #define lli long long int #define ld long double #define REP(i, n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end(); #define rall(x) x.rbegin(), x.rend() #define pb push_back #define MP make_pair using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 2e5 + 5; const int INF = 1e9 + 500; const int MOD = 1e9 + 7; int n, q; vector<vector<int> > adj(N, vector<int>()); int ans = 0; int dfs(int node, int par) { if(adj[node].size() == 1 && par) { ans++; // cout << "node: " << node << " 1" << "\n"; return 1; } int ret = 0; if(par == 0 && adj[node].size() == 1) ret++; for(auto c : adj[node]) { if(c == par) continue; ret += dfs(c, node); } // cout << "node: " << node << " ret:" << ret << "\n"; if(par == 0) { if(ret & 1) return -1; return ans; } if(ret & 1) { ans++; return 1; } else { ans += 2; return 2; } } void solve() { cin >> n >> q; REP(i, n - 1) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } REP(z, q) { int d; cin >> d; ans = 0; // fill(dp.begin(), dp.begin() + n + d + 3, 0); for(int i = n + 1; i <= n + d; i++) { int x; cin >> x; adj[i].pb(x); adj[x].pb(i); } int res = dfs(1, 0); cout << res << "\n"; for(int i = n + 1; i <= n + d; i++) { for(auto j : adj[i]) { adj[j].pop_back(); } adj[i].clear(); } } } signed main() { fastio(); solve(); }
#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...