Submission #1270527

#TimeUsernameProblemLanguageResultExecution timeMemory
1270527goldencheemsSpring cleaning (CEOI20_cleaning)C++20
9 / 100
26 ms7356 KiB
#include <bits/stdc++.h>
#define ford(i,x,y) for(int i=x;i<=y;++i)
#define forr(i,x,y) for(int i=x;i>=y;--i)
#define ll long long
#define ld long double
#define isz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
const int N=1e5+10;
int n, q, deg[N];
vector <int> G[N<<1];
void sub1(){
    int leaf=0;
    ford (i, 1, n)
        if (deg[i]==1)++leaf;
    int d; cin>>d;
    vector <int> uv(d), cnt(n+1, 0);
    ford (i, 0, d-1){
        cin>>uv[i];
        ++leaf;
        if (!cnt[uv[i]])--leaf;
        ++cnt[uv[i]];
    }
    if (leaf&1){
        cout<<-1;
        return;
    }
    int cnt1=0, cnt2=0;
    ll ans=0;
    ford (i, 2, n){
        if (cnt[i]>2){
            int k=(cnt[i]-1)/2;
            cnt[i]-=k*2;
            ans+=k*2;
        }
        if (!cnt[i])++cnt1;
        else cnt2+=cnt[i];
    }
    int mn=min(cnt1, cnt2);
    ans+=3*mn;
    cnt1-=mn;
    cnt2-=mn;
    ans+=cnt1;
    ans+=cnt2*2;
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    ford (i, 2, n){
        int u, v;
        cin>>u>>v;
        G[u].pb(v);
        G[v].pb(u);
        ++deg[u];
        ++deg[v];
    }
    sub1();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...