Submission #578093

#TimeUsernameProblemLanguageResultExecution timeMemory
578093talant117408Spring cleaning (CEOI20_cleaning)C++17
0 / 100
1016 ms15188 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' const int N = 2e5+7; vector <vector <int>> graph(N), new_graph(N); int used[N], depth[N], root; ll ans; vector <pii> dfs(int v, int p) { vector <pii> leaves; for (auto to : new_graph[v]) { if (to == p) { continue; } depth[to] = depth[v] + 1; auto tmp = dfs(to, v); for (auto x : tmp) leaves.pb(x); } sort(all(leaves), [&](pii a, pii b) { return depth[a.first] < depth[b.first]; }); if (v == root) { if (sz(leaves)&1) return leaves; for (int i = 0; i < sz(leaves); i++) { auto x = leaves[i]; ans += depth[x.first]-depth[v]; } return vector <pii> (0); } else { if (sz(leaves) == 0) { leaves.pb(mp(v, v)); return leaves; } vector <pii> ret; ret.pb(mp(leaves.back().first, v)); leaves.pop_back(); if (sz(leaves)&1) { ret.pb(mp(leaves.back().first, v)); leaves.pop_back(); } for (int i = 0; i < sz(leaves); i++) { auto x = leaves[i]; ans += depth[x.first]-depth[v]; } return ret; } } int get(int n) { ans = 0; for (int i = 1; i <= n; i++) { used[i] = 0; if (sz(new_graph[i]) > 1) { root = i; } } auto tmp = dfs(root, root); if (sz(tmp)) return -1; else return ans; } void solve() { int n, q; cin >> n >> q; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; graph[a].pb(b); graph[b].pb(a); } if (n <= 20000 && q <= 300) { while (q--) { int vertex = n+1; int k; cin >> k; for (int i = 1; i <= n+k; i++) { new_graph[i].clear(); for (auto to : graph[i]) new_graph[i].pb(to); } while (k--) { int x; cin >> x; new_graph[x].pb(vertex); new_graph[vertex].pb(x); vertex++; } cout << get(vertex-1) << endl; } } } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } return 0; }
#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...