Submission #1270216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270216		thanhcodedao	Spring cleaning (CEOI20_cleaning)	C++20	9 / 100	1097 ms	31560 KiB

cleaning

#include <bits/stdc++.h>
#define N 100000
#define pb push_back
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define ii pair<int, int>
#define M 1000000007
#define int long long
#define el '\n'
#define bit(mark, i) ((mark >> i) & 1)
using namespace std;

int n, q,  up[N + 5][20], h[N + 5];
vector <int> g[N + 5];
vector <int> d, e;
void dfs(int u, int p){
    int t = 0;
    for (auto v : g[u]) if (v != p){
        t++;
        dfs(v, u);
    }
    if (t == 0) d.pb(u);
}

void sub1(){
    int ans = 1;
    bool ok = true;
    if (d.size() % 2 == 1){
        ok = false;
    }
    else{
        int cap = d.size() / 2;
        ans += (cap - 1) * 2;
    }
    //cout << ans << el;
    while (q--){
        int m; cin >> m;
        fu(i, 1, m){
            int x; cin >> x;
        }
        if (!ok) cout << -1 << el;
        else{
            cout << ans + m << el;
        }
    }
}

void dfs1(int u, int p){
    for (auto v : g[u]) if (v != p){
        h[v] = h[u] + 1;
        up[v][0] = u;
        dfs1(v, u);
    }
}

int lca(int u, int v){
    if (h[u] < h[v]) swap(u, v);
    int k = h[u] - h[v];
    fd(i, 19, 0){
        if (bit(k, i)){
            u = up[u][i];
        }
    }
    if (u == v) return u;
    fd(i, 19, 0){
        if (up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}
int dist(int u, int v, int l){
    return h[u] + h[v] - 2 * h[l];
}
 map <int, int> mp;
bool cmp(int x, int y){

    return h[x] + mp[x] < h[y] + mp[y];
}
int dem[N + 5];
void sub2(){
    sort(d.begin(), d.end());
    fu(i, 1, q){
        int m; cin >> m;
        vector <int> a = d;
        vector <int> c(m);

        int cnt = 0;
        fu(i, 1, m){
            int x; cin >> x;

            auto it = lower_bound(d.begin(), d.end(), x);
            if (it == d.end() || *it != x || dem[x]) a.pb(x), mp[x] = 1;
            else{
                int pos = it - d.begin();
                a[pos] = x;
                dem[x]++;
            }
            cnt++;
        }

        sort(a.begin(), a.end(), cmp);
//        for (auto x : a) cout << x << ' ';
//        cout << el;
        int ans = 0;
        if (a.size() % 2 == 1){
            cout << -1 << el;
            continue;
        }
        int len = a.size();
        int l = lca(a[0], a[len - 1]);
        ans += dist(a[0], a[len - 1], l);
     //   cout << a[0] << ' ' << a[len - 1] << ' ' << l << ' ' <<  dist(a[0], a[len - 1], l) << el;
        for (int i = 1; i < len - 1; i += 2){
            int u = a[i], v = a[i + 1];
            int l = lca(u, v);
            int s = dist(u, v, l);
            ans += s;
       //     cout << u << ' ' << v << ' ' << l << ' ' << s<< el;
        }
        mp.clear();
        memset(dem, 0, sizeof(dem));
      //  cout << ans << el;
        cout << ans + cnt << el;
    }
}
signed main(){
//    freopen("crt.inp", "r", stdin);
//    freopen("crt.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    vector <int> t;
    fu(i, 2, n){

        int u, v; cin >> u >> v;
        if (u > v) swap(u, v);
        g[u].pb(v);
        g[v].pb(u);
        if (u == 1) t.pb(v);
    }
    d.pb(1);
    dfs(1, 0);
    e = d;
    sort(e.begin(), e.end());
//    for (auto x : d) cout << x << ' ';
//    cout << el;
    if (t.size() == n - 1){
        sub1();
    }
    dfs1(1, 0);
    fu(i, 1, 19){
        fu(j, 1, n){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    sub2();
}

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