Submission #1270525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270525		goldencheems	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	63 ms	21696 KiB

cleaning

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=1e9+7;
const ll inf=1e18;
const int N=1e5+2;
int maxmize(int a,int b){
    return a>b?a:b;
}
int minmize(int a,int b){
    return a<b?a:b;
}
ll Maxmize(ll a,ll b){
    return a>b?a:b;
}
ll Minmize(ll a,ll b){
    return a<b?a:b;
}
int add(int a,int b){
    a=(a+b)%MOD;
    if(a<0)
        a+=MOD;
    return a;
}
int mul(int a,int b){
    return 1LL*a*b%MOD;
}
int pow_mod(int a,int b){
    int s=1;
    while(b){
        if(b&1)
            s=mul(s,a);
        a=mul(a,a);
        b>>=1;
    }
    return s;
}
int n,q,deg[N],p[N][20],lg,d[N],dau,vi[N],L[N],cnt[N];
vector<int>adj[N];
bool leaf[N],ok[N],sus[10],con[N];
vector<int>Q[N],las;
void DFS(int u,int f){
    for(auto&v:adj[u])
        if(v!=f){
            p[v][0]=u;
            d[v]=d[u]+1;
            DFS(v,u);
        }
}
int LCK(int u,int v){
    if(d[u]<d[v])
        swap(u,v);
    for(int i=lg;i>=0;--i)
        if(d[p[u][i]]>=d[v])
            u=p[u][i];
    if(u==v)
        return v;
    for(int i=lg;i>=0;--i)
        if(p[u][i]!=p[v][i]){
            u=p[u][i];
            v=p[v][i];
        }
    return p[u][0];
}
int dist(int u,int v){
    return d[u]+d[v]- (d[LCK(u,v)]<<1);
}
void pre_LCK(){
    for(lg=1;(1<<lg)<=n;++lg);
    --lg;
    p[1][0]=1;
    DFS(1,0);
    for(int i=1;i<=lg;++i)
        for(int u=1;u<=n;++u)
            p[u][i]=p[p[u][i-1]][i-1];
}
bool cmp(int x,int y){
    return d[x]>d[y];
}
void sub1(){
    int ans=0;
    for(int Qi=1;Qi<=q;++Qi){
        int re=0,tru=0;
        for(auto&v:Q[Qi]){
            ++cnt[v];
            if(leaf[v]){
                ++re;
                if(!ok[v]){
                    --tru;
                    ok[v]=true;
                }
            }
            else
                 ++re;
        }
        int la=dau+re+tru;
        for(auto&v:Q[Qi])
            ok[v]=false;
        if(la&1){
            cout<<-1<<'\n';
            return;
        }
    }
    int dem=0;
    for(int i=2;i<=n;++i)
        if(cnt[i]&1){
            ++dem;
            ans+=(cnt[i]-1);
        }
        else if(cnt[i]>0){
            con[i]=true;
            ans+=(cnt[i]-2);
        }
    vector<int>trong;
    for(int u=2;u<=n;++u)
        if(con[u])
            trong.push_back(u);
    ans+=4*trong.size();
    if(dem&1){
        ans+=3;
        ans+=4*(dem-1)/2;
    }
    else
        ans+=2*dem+3;
    vector<int>luu;
    for(int u=2;u<=n;++u)
        if(cnt[u]==0)
            luu.push_back(u);
    ans+=(luu.size());
    if(dem&1)
        --ans;
    //cerr<<luu.size()<<'\n';
    cout<<ans;
}
void sub3(){
    sort(las.begin(),las.end(),cmp);
    int ans=0;
    for(int i=0;i+1<las.size();i+=2)
        ans+=dist(las[i],las[i+1]);
        for(int Qi=1;Qi<=q;++Qi){
            int re=0,tru=0,res=ans;
            for(auto&v:Q[Qi]){
                ++cnt[v];
                if(leaf[v]){
                    ++re;
                    if(!ok[v]){
                        --tru;
                        ok[v]=true;
                    }
                }
                else
                        ++re;
            }
            int la=dau+re+tru;
            for(auto&v:Q[Qi])
                ok[v]=false;
            if(la&1){
                cout<<-1<<'\n';
                continue;
            }
            if(LCK(las[0],Q[Qi][1])==Q[Qi][1])
                res+=2;
            else
                res+=dist(las[0],Q[Qi][1])+1;
            cout<<res<<'\n';
        }

}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>q;
    memset(sus,true,sizeof(sus));
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        ++deg[u];
        ++deg[v];
    }
    for(int u=1;u<=n;++u)
        if(deg[u]==1){
            leaf[u]=true;
            ++dau;
            las.push_back(u);
        }
    pre_LCK();
    for(int Qi=1;Qi<=q;++Qi){
        cin>>L[Qi];
        for(int k=1;k<=L[Qi];++k){
            int v;
            cin>>v;
            Q[Qi].push_back(v);
            if(v==1)
                sus[1]=false;
        }
        if(L[Qi]!=1)
            sus[3]=false;
    }
    for(int i=2;i<=n;++i)
        if(deg[i]>2)
            sus[1]=false;
    if(sus[1]&&q==1)
        sub1();
    else if(sus[3])
        sub3();
    else
        sub3();
    return 0;
}
/*
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
1 6
1 1

7 3
1 2
2 4
4 5
5 6
5 7
3 4
4 1 1 2 6
3 6 6 2
2 2 7

7 1
1 2
1 3
1 4
1 5
1 6
1 7
4 2 3 4 4
*/

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