Submission #1270979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270979		thanhcodedao	Spring cleaning (CEOI20_cleaning)	C++20	18 / 100	144 ms	21572 KiB

cleaning

/*Dep trai co j sai*/
/*IOI here we go*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pu push_back
const int N=1e5;
ll mod=1e9+7,oo=1e18;
int n,q,d[N+10],tt[22][N+10],cnt,in[N+10],sz[N+10];
vector <int> adj[N+10];
int a[N+10];
vector <int> la;
bool o[N+10],g[N+10];
void dfs(int u,int p){
    in[u]=++cnt;
    for(int v:adj[u]){
        if(v==p) continue;
        tt[0][v]=u;
        d[v]=d[u]+1;
        dfs(v,u);
    }
    }
int lca(int u,int v){
    if(d[u]<d[v]) swap(u,v);
    for(int i=20;i>=0;--i){
        int pu=tt[i][u];
        if(d[pu]>=d[v]) u=pu;
    }
    if(u==v) return u;
    for(int i=20;i>=0;--i){
        int pu=tt[i][u],pv=tt[i][v];
        if(pu!=pv){
            u=pu;
            v=pv;
        }
    }
    return tt[0][u];
    }
bool cmp(int a,int b){

    return in[a]<in[b];
    }
bool cmp2(int a,int b){
    if(d[a]!=d[b]) return d[a]<d[b];
    return in[a]<in[b];
    }
void sub1(){
    sort(la.begin(),la.end(),cmp2);
    int res=0;
    int m=la.size();
    for(int i=0;i<m/2;i++){
            int u=la[i],v=la[m-i-1];
            int x=lca(u,v);
            //cout<<u<<" "<<v<<" "<<x<<" "<<d[u]+d[v]-2*d[x]<<'\n';
            res+=d[u]+d[v]-2*d[x];
        }
    while(q--){
        int D;
        cin>>D;
        int ans=0;
        vector <int> l;
        for(int i=1;i<=D;i++) {cin>>a[i];
            ans++;
            sz[a[i]]++;
            if(!g[a[i]]){
                l.pu(a[i]);
                g[a[i]]=true;
            }
        }
        for(int i=1;i<=D;i++){
            if(sz[a[i]]%2==0){
                l.pu(a[i]);
                sz[a[i]]--;
            }
        }
        if(la.size()%2==1){
            l.pu(la[la.size()/2]);
        }
        sort(l.begin(),l.end(),cmp);
        int m=l.size();
       // cout<<m<<" ";
       // for(int u:l) cout<<u<<' ';
       // cout<<'\n';
        if(m%2==1){
            for(int i=1;i<=D;i++){
                g[a[i]]=o[a[i]];
                sz[a[i]]=0;
            }
            cout<<-1<<'\n';
            continue;
        }
        for(int i=0;i<m-1;i+=2){
            int u=l[i],v=l[i+1];
            int x=lca(u,v);
            //cout<<u<<" "<<v<<" "<<x<<" "<<d[u]+d[v]-2*d[x]<<'\n';
            ans+=d[u]+d[v]-2*d[x];
        }
        for(int i=1;i<=D;i++){
                g[a[i]]=o[a[i]];
                sz[a[i]]=0;
            }
        cout<<ans+res<<'\n';
    }
    }
void tinh(){
    cin>>n>>q;
    //for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pu(v);
        adj[v].pu(u);
    }
    for(int i=1;i<=n;i++) if(adj[i].size()==1) {la.pu(i);
        o[i]=g[i]=true;
    }
    d[1]=1;
    dfs(1,0);
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++) tt[i][j]=tt[i-1][tt[i-1][j]];
    }
    sub1();
    }
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen("crt.inp","r",stdin);
//    freopen("crt.out","w",stdout);
    tinh();
    return 0;
    }

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