Submission #1002395

#TimeUsernameProblemLanguageResultExecution timeMemory
1002395yoav_sSpring cleaning (CEOI20_cleaning)C++17
0 / 100
55 ms35920 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") using namespace std; typedef int ll; typedef vector<ll> v; typedef vector<v> vv; typedef vector<vv> vvv; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; typedef pair<ll,ll> p; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef pair<ll, p> tri; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; #define f first #define s second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() const ll INF = 1e18; const ll mod = 1e9 + 7; #define set unordered_set ll getLeafCount(ll i, vv &graph, v &res) { if (res[i] != -1) return 0; res[i] = 0; if (graph[i].size() == 1) { res[i] = 1; return 1; } for (ll x : graph[i]) res[i] += getLeafCount(x, graph, res); return res[i]; } void getOddAndEvenParents(ll i, vv &graph, v &oddRes, v &evenRes, ll oddParents, ll evenParents, v &parity) { if (oddRes[i] != -1) return; if (parity[i] % 2 == 0) evenParents++; else oddParents++; oddRes[i] = oddParents; evenRes[i] = evenParents; for (ll x : graph[i]) getOddAndEvenParents(x, graph, oddRes, evenRes, oddParents, evenParents, parity); } set<ll> *solve(ll i, vv &graph, vb &visited, v &res, vv &changes, v &oddParents, v &evenParents) { visited[i] = true; vector<set<ll>*> childrenSets; for (ll x : graph[i]) { if (visited[x]) continue; childrenSets.pb(solve(x, graph, visited, res, changes, oddParents, evenParents)); } childrenSets.pb(new set<ll>()); for (ll x : changes[i]) { (*childrenSets.back()).insert(x); res[x] += oddParents[i] - evenParents[i]; } set<ll> *baseSet = new set<ll>(); ll maxiSize = -1; ll index = -1; for (ll i = 0; i < childrenSets.size(); i++) { if ((*childrenSets[i]).size() > maxiSize) { baseSet = childrenSets[i]; maxiSize = (*childrenSets[i]).size(); index = i; } } set<ll> newAdditions; for (ll j = 0; j < childrenSets.size(); j++) { if (j == index) continue; for (auto y : (*childrenSets[j])) { if ((*baseSet).count(y) > 0) { res[y] -= oddParents[i] - evenParents[i]; } else { (*baseSet).insert(y); newAdditions.insert(y); } } } for (ll x : newAdditions) (*baseSet).erase(x); set<ll> done; for (ll j = 0; j < childrenSets.size(); j++) { if (j == index) continue; for (auto y : *childrenSets[j]) { if ((*baseSet).count(y) > 0) { (*baseSet).erase(y); done.insert(y); res[y] += evenParents[i] - oddParents[i]; } else { (*baseSet).insert(y); if (done.count(y) > 0) res[y] += oddParents[i] - evenParents[i]; } } delete childrenSets[i]; } return baseSet; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll N, Q; cin >> N >> Q; vv graph(N); for (ll i = 0; i < N - 1; i++) { ll a, b; cin >> a >> b; a--; b--; graph[a].pb(b); graph[b].pb(a); } ll root = 0; while (graph[root].size() == 1) root++; v leafCount(N, -1); getLeafCount(root, graph, leafCount); v oddParents(N, -1), evenParents(N, -1); getOddAndEvenParents(root, graph, oddParents, evenParents, 0, 0, leafCount); vv queries(Q); for (ll i = 0; i < Q; i++) { ll amt; cin >> amt; for (ll j= 0; j < amt; j++) { ll par; cin >> par; par--; queries[i].pb(par); } } vv changedInQueries(N); for (ll i = 0 ;i < Q; i++) { map<ll, ll> changed; for (ll x : queries[i]) { changed[x]++; } for (auto x : changed) { if ((x.s % 2 == 1) ^ (graph[x.f].size() == 1)) changedInQueries[x.f].pb(i); } } v addToQuery(Q); ll base = N - 2; for (ll i = 0 ;i < N; i++) if (leafCount[i] % 2 == 0) base++; vb visited(N, false); solve(root, graph, visited, addToQuery, changedInQueries, oddParents, evenParents); for (ll i = 0; i < Q; i++) { ll count = leafCount[root] + queries[i].size(); set<ll> changed; for (ll x : queries[i]) if (graph[x].size() == 1) changed.insert(x); count -= changed.size(); if (count % 2 == 1) cout << "-1\n"; else cout << base + queries[i].size() + addToQuery[i] << "\n"; } return 0; }

Compilation message (stderr)

cleaning.cpp:28:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   28 | const ll INF = 1e18;
      |                ^~~~
cleaning.cpp: In function 'std::unordered_set<int>* solve(ll, vv&, vb&, v&, vv&, v&, v&)':
cleaning.cpp:73:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::unordered_set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (ll i = 0; i < childrenSets.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:75:39: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   75 |         if ((*childrenSets[i]).size() > maxiSize)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
cleaning.cpp:83:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::unordered_set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (ll j = 0; j < childrenSets.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:101:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::unordered_set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (ll j = 0; j < childrenSets.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
#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...