Submission #945549

#TimeUsernameProblemLanguageResultExecution timeMemory
945549berrSpring cleaning (CEOI20_cleaning)C++17
100 / 100
108 ms25780 KiB
#include <bits/stdc++.h> using namespace std; const int N=2e5; vector<vector<int>> g(N); vector<int> tin(N), c(N), tout(N); int leafs; struct LCA { int root, n, cnt; vector<array<int, 21>> par; vector<int> d; LCA(int _n, int r){ n = _n; par.resize(n); d.assign(n, 0); root = r; cnt = 0; d[root] = -1; dfs(root, root); for (int i = 1; i < 21; i++){ for(int l = 0; l<n; l++){ par[l][i] = par[par[l][i-1]][i-1]; } } } void dfs(int v, int p){ par[v][0] = p; tin[v] = cnt++; d[v] = d[p]+1; for (auto i: g[v]){ if (i != p) dfs(i, v), c[v]+=c[i]; } if(g[v].size()==1) c[v]++, leafs++; tout[v] = cnt++; } bool ia(int u, int v){ return tin[u] <= tin[v] && tout[u] >= tout[v]; } int operator()(int u, int v){ if(ia(u, v)) return u; if(ia(v, u)) return v; for(int i = 20; i>=0; i--){ if(!ia(par[u][i], v)) u=par[u][i]; } return par[u][0]; } int distance(int u, int v){ return d[u]+d[v]-2*d[(*this)(u, v)]; } }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<array<int, 2>> count(n); int root=0; for(int i =0; i<n-1; i++){ int x, y; cin >> x >> y; x--; y--; g[x].push_back(y); g[y].push_back(x); if(g[x].size()>1) root = x; if(g[y].size()>1) root = y; } LCA lca(n, root); int ans = 0; auto dfs2=[&](int v, int p, auto&& dfs2)->void{ //cout<<v+1<<" "<<c[v]<<"\n"; if(c[v] %2) count[v][1]++; else count[v][0]++, ans++; for(auto i: g[v]){ if(i!=p){ count[i][0]+=count[v][0]; count[i][1]+=count[v][1]; dfs2(i, v, dfs2); } } }; dfs2(root, root, dfs2) ; int tmpans = ans, tmpleafs=leafs; while(q--){ int d; cin >> d; vector<int> ar(d),a, up; for(auto &i: ar) cin >> i, i--; sort(ar.begin(), ar.end(), [&](int x, int y){ return tin[x] < tin[y]; }); int k=1; for(int i=1; i<d; i++){ if(ar[i]==ar[i-1])k++; else{ if(g[ar[i-1]].size()==1){ leafs+=k-1; if(k%2==0) a.push_back(ar[i-1]); k = 1; } else{ leafs+=k; if(k%2==1) a.push_back(ar[i-1]); k=1; } } } if(g[ar[d-1]].size()==1){ leafs+=k-1; if(k%2==0) a.push_back(ar[d-1]); } else{ leafs+=k; if(k%2==1) a.push_back(ar[d-1]); } up = a; if(up.size()){ for(int i=0; i<a.size()-1; i++){ up.push_back(lca(a[i], a[i+1])); } sort(up.begin(), up.end(), [&](int x, int y){ return tin[x] < tin[y]; }); vector<int> upp; for(int i=0; i<up.size(); i++){ if(i==0||up[i]!=up[i-1]) upp.push_back(up[i]); } up=upp; upp.clear(); if(up.size()){ stack<int> st; st.push(0); vector<int> p(up.size()), v(up.size()), s(up.size()); vector<vector<int>> adj(up.size()); vector<int> aa(up.size()); sort(up.begin(), up.end(), [&](int x, int y){ return tin[x] < tin[y]; }); for(int i=1; i<up.size(); i++) { while(st.size() && tout[up[st.top()]] < tin[up[i]]){ st.pop(); } if(st.size()) adj[st.top()].push_back(i), aa[i]++, p[i]=st.top(); else p[i]=i; st.push(i); } auto dfsa=[&](int ve, auto&&dfsa)->void{ for(auto i: adj[ve]){ dfsa(i, dfsa), v[ve]+=v[i]; } }; int pos=0; for(int l=0; l<a.size(); l++){ while(pos<up.size()&&up[pos]!=a[l]) pos++; if(pos<up.size()&&up[pos]==a[l]) v[pos]++; } for(int i=0; i<up.size(); i++){ if(aa[i]==0) dfsa(i, dfsa); } for(int i=0; i<up.size(); i++){ if(p[i]==i){ auto x = count[up[i]]; if(v[i]%2){ ans-=x[0]; ans+=x[1]; } } else if(v[i]%2){ auto x=count[up[i]], y=count[up[p[i]]]; x[0]-=y[0]; x[1]-=y[1]; ans-=x[0]; ans+=x[1]; } } } } if((leafs%2)!=0) cout<<-1<<"\n"; else cout<<ans-1+d+n-1<<"\n"; ans=tmpans; leafs=tmpleafs; } }

Compilation message (stderr)

cleaning.cpp: In function 'int32_t main()':
cleaning.cpp:141:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             for(int i=0; i<a.size()-1; i++){
      |                          ~^~~~~~~~~~~
cleaning.cpp:152:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             for(int i=0; i<up.size(); i++){
      |                          ~^~~~~~~~~~
cleaning.cpp:171:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |                 for(int i=1; i<up.size(); i++) {
      |                              ~^~~~~~~~~~
cleaning.cpp:188:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |                 for(int l=0; l<a.size(); l++){
      |                              ~^~~~~~~~~
cleaning.cpp:189:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |                     while(pos<up.size()&&up[pos]!=a[l]) pos++;
      |                           ~~~^~~~~~~~~~
cleaning.cpp:190:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |                     if(pos<up.size()&&up[pos]==a[l]) v[pos]++;
      |                        ~~~^~~~~~~~~~
cleaning.cpp:193:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |                 for(int i=0; i<up.size(); i++){
      |                              ~^~~~~~~~~~
cleaning.cpp:199:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |                  for(int i=0; i<up.size(); i++){
      |                               ~^~~~~~~~~~
#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...