Submission #945535

#	Time	Username	Problem	Language	Result	Execution time	Memory
945535		berr	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	145 ms	86608 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 

template <class T>
struct RMQ { // 0-based
  vector<vector<T>> rmq;
  T kInf = numeric_limits<T>::max();
  void build(const vector<T>& V) {
    int n = V.size(), on = 1, dep = 1;
    while (on < n) on *= 2, ++dep;
    rmq.assign(dep, V);
 
    for (int i = 0; i < dep - 1; ++i)
      for (int j = 0; j < n; ++j) {
        rmq[i + 1][j] = min(rmq[i][j], rmq[i][min(n - 1, j + (1 << i))]);
      }
  }
  T query(int a, int b) { // [a, b)
    if (b <= a) return kInf;
    int dep = 31 - __builtin_clz(b - a); // log(b - a)
    return min(rmq[dep][a], rmq[dep][b - (1 << dep)]);
  }
};

struct LCA { // 0-based
int n, root;
  vector<int> enter, depth, exxit;
  vector<vector<int>> G;
  vector<pair<int, int>> linear;
  RMQ<pair<int, int>> rmq;
  int timer = 0;
  LCA() {} 
  LCA(vector<vector<int>> g, int root)  {
    n = g.size();
    enter.resize(n, -1),
    exxit.resize(n, -1); 
    depth.resize(n);
    G=g;
    linear.resize(2 * n);

    build(root);
  }
  void dfs(int node, int dep) {
    linear[timer] = {dep, node};
    enter[node] = timer++;
    depth[node] = dep;
    for (auto vec : G[node])
    if (enter[vec] == -1) {
      dfs(vec, dep + 1);
      linear[timer++] = {dep, node};
    }
    exxit[node] = timer;
  }
  void add_edge(int a, int b) {
    G[a].push_back(b);
    G[b].push_back(a);
  }
  void build(int root) {
    dfs(root, 0);
    rmq.build(linear);
  }
  int query(int a, int b) {
    a = enter[a], b = enter[b];
    return rmq.query(min(a, b), max(a, b) + 1).second;
  }
  int dist(int a, int b) {
    return depth[a] + depth[b] - 2 * depth[query(a, b)];
  }
};
 
int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    int n, q; cin >> n >> q;
 
    vector<vector<int>> g(n+5);
    vector<int> c(n);
    vector<array<int, 2>> count(n);
    int leafs=0, 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(g, root);
    vector<int> vis(n), tin(n), tout(n);
 
    int cnt = 0;
    auto dfs=[&](int v, int p, auto&& dfs)->void{
        tin[v] = cnt++;
        for(auto i: g[v])
            if(i!=p) dfs(i, v, dfs), c[v]+=c[i];
        
        if(g[v].size()==1) c[v]++, leafs++;
        else vis[v] = 1;
 
        tout[v] = cnt++;
    };
    
    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);
            }
        }
    };
 
    dfs(root, root, dfs);
    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; 
        int check =0;
        if(up.size()){
           
            for(int i=0; i<a.size()-1; i++){
                up.push_back(lca.query(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;
            if(up.size()){
                stack<int> st;
 
                st.push(0);
 
                vector<int> p(up.size()), v(up.size());
                vector<vector<int>> adj(up.size());
                vector<int> aa(up.size());
 
                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, int p, auto&&dfsa)->void{
 
                    for(auto i: adj[ve]){
                        if(i!=p) dfsa(i, ve, 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, i, dfsa);
                }
 
 
 
                 for(int i=0; i<up.size(); i++){
                    if(p[i]==i){
                        auto x = count[up[i]];
                        if(v[i]%2){
                            check=1;
                            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:168:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             for(int i=0; i<a.size()-1; i++){
      |                          ~^~~~~~~~~~~
cleaning.cpp:179:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |             for(int i=0; i<up.size(); i++){
      |                          ~^~~~~~~~~~
cleaning.cpp:192:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |                 for(int i=1; i<up.size(); i++) {
      |                              ~^~~~~~~~~~
cleaning.cpp:210:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |                 for(int l=0; l<a.size(); l++){
      |                              ~^~~~~~~~~
cleaning.cpp:211:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |                     while(pos<up.size()&&up[pos]!=a[l]) pos++;
      |                           ~~~^~~~~~~~~~
cleaning.cpp:212:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |                     if(pos<up.size()&&up[pos]==a[l]) v[pos]++;
      |                        ~~~^~~~~~~~~~
cleaning.cpp:215:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |                 for(int i=0; i<up.size(); i++){
      |                              ~^~~~~~~~~~
cleaning.cpp:221:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |                  for(int i=0; i<up.size(); i++){
      |                               ~^~~~~~~~~~
cleaning.cpp:165:13: warning: variable 'check' set but not used [-Wunused-but-set-variable]
  165 |         int check =0;
      |             ^~~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30