Submission #701806

#	Time	Username	Problem	Language	Result	Execution time	Memory
701806		Darren0724	Spring cleaning (CEOI20_cleaning)	C++17	34 / 100	1077 ms	29388 KiB

cleaning

#pragma GCC optimize("Ofast","O3")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
vector<vector<int>> adj(200010);
vector<vector<int>> dp;
int ans=0;
void dfs(int k,int pa,int dis){
    if(adj[k].size()==1){
        dp[k].push_back(dis);
        return;
    }
    for(int j:adj[k]){
        if(j==pa){
            continue;
        }
        dfs(j,k,dis+1);
        for(int i:dp[j]){
            dp[k].push_back(i);
        }
    }
    while(dp[k].size()>2){
        int a=dp[k].back();
        dp[k].pop_back();
        int b=dp[k].back();
        dp[k].pop_back();
        ans+=a+b-dis*2;
    }
    if(k==0){
        if(dp[k].size()==2){
            ans+=dp[k][0]+dp[k][1]-dis*2;
        }
        else{
            ans=-1;
        }
    }
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=0;i<q;i++){
        int d;cin>>d;
        vector<int> a(d);
        int cnt1=n;
        for(int j=0;j<d;j++){
            int p;cin>>p;p--;
            a[j]=p;
            adj[p].push_back(cnt1);
            adj[cnt1].push_back(p);
            cnt1++;
        }
        ans=0;
        if(adj[0].size()==1){
            a.push_back(0);
            adj[0].push_back(cnt1);
            adj[cnt1].push_back(0);
            cnt1++;
            d++;
            ans=-1;
        }
        dp.clear();
        dp.resize(cnt1);
        dfs(0,0,0);
        cout<<ans<<'\n';
        for(int j=0;j<d;j++){
            adj[a[j]].pop_back();
            adj[--cnt1].pop_back();
        }
    }
 
    return 0;
}

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