Submission #945533

#	Time	Username	Problem	Language	Result	Execution time	Memory
945533		berr	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	130 ms	41172 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
struct LCA {                                                
        int root, n, cnt;
 
        vector<vector<int>> adj;  
        vector<array<int, 21>> par;
        vector<int> ti, to, d;
 
        LCA(vector<vector<int>> aadj, int r){ 
            adj = aadj; n = adj.size();
            par.resize(n);
            d.assign(n, 0);
            root = r; cnt = 0;
            ti.resize(n); to.resize(n);
 
            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;
            ti[v] = cnt++;
            d[v] = d[p]+1;
            for (auto i: adj[v]){
                if (i != p) dfs(i, v); 
            }
            to[v] = cnt++;
        }
 
        bool ia(int u, int v){
            return ti[u] <= ti[v] && to[u] >= to[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<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(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:155: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]
  155 |             for(int i=0; i<a.size()-1; i++){
      |                          ~^~~~~~~~~~~
cleaning.cpp:166: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]
  166 |             for(int i=0; i<up.size(); i++){
      |                          ~^~~~~~~~~~
cleaning.cpp:179: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]
  179 |                 for(int i=1; i<up.size(); i++) {
      |                              ~^~~~~~~~~~
cleaning.cpp:197: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]
  197 |                 for(int l=0; l<a.size(); l++){
      |                              ~^~~~~~~~~
cleaning.cpp:198: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]
  198 |                     while(pos<up.size()&&up[pos]!=a[l]) pos++;
      |                           ~~~^~~~~~~~~~
cleaning.cpp:199: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]
  199 |                     if(pos<up.size()&&up[pos]==a[l]) v[pos]++;
      |                        ~~~^~~~~~~~~~
cleaning.cpp:202: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]
  202 |                 for(int i=0; i<up.size(); i++){
      |                              ~^~~~~~~~~~
cleaning.cpp:208: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]
  208 |                  for(int i=0; i<up.size(); i++){
      |                               ~^~~~~~~~~~
cleaning.cpp:152:13: warning: variable 'check' set but not used [-Wunused-but-set-variable]
  152 |         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