Submission #1208258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208258		Zbyszek99	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	81 ms	25040 KiB

cleaning

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vi graph[100'001];
int leafs[100'001];
int path0[100'001];
int depth[100'001];
int pre[100'001];
int max_pre[100'001];
int jump[100'001][17];

vi sons[100'001];
int is_change[100'001];

int cur_pre;
int def_ans;
int total_leafs;
int ans;

int dfs(int v, int pop)
{
    if(siz(graph[v]) == 1) 
    {
        leafs[v] = 1;
        total_leafs++;
    }
    jump[v][0] = pop;
    depth[v] = depth[pop]+1;
    pre[v] = cur_pre++;
    max_pre[v] = pre[v];
    forall(it,graph[v])
    {
        if(it != pop)
        {
            leafs[v] += dfs(it,v);
            leafs[v] %= 2;
            max_pre[v] = max_pre[it];
        }
    }
    if(leafs[v] == 0 && v != pop) 
    {
        path0[v] = 1;
        def_ans++;
    }
    return leafs[v];
}

void dfspath(int v, int pop)
{
    path0[v] += path0[pop];
    forall(it,graph[v])
    {
        if(it != pop)
        {
            dfspath(it,v);
        }
    }
}

int lca(int a, int b)
{
    if(pre[a] <= pre[b] && max_pre[a] >= pre[b]) return a;
    for(int bit = 16; bit >= 0; bit--)
    {
        if(max_pre[jump[a][bit]] < pre[b] || pre[jump[a][bit]] > pre[b])
        {
            a = jump[a][bit];
        }
    }
    return jump[a][0];
}

int dfs_ans(int v, int pop)
{
    int h = is_change[v];
    forall(it,sons[v])
    {
        h += dfs_ans(it,v);
    }
    if(h % 2 == 1)
    {
        int len = depth[v] - depth[pop];
        int zero = path0[v] - path0[pop];
        ans += len - 2*zero;
    }
    return h;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,q;
    cin >> n >> q;
    rep(i,n-1)
    {
        int a,b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    int root = 1;
    rep2(i,1,n) if(siz(graph[i]) == 1) root = i;
    dfs(root,root);
    dfspath(root,root);
    rep2(bit,1,16)
    {
        rep2(i,1,n)
        {
            jump[i][bit] = jump[jump[i][bit-1]][bit-1];
        }
    }
    unordered_map<int,int> new_tree;
    vector<pii> verts_pom;
    set<pii> new_sons;
    rep(qq,q)
    {
        int d;
        cin >> d;
        new_tree = {};
        rep(j,d)
        {
            int x;
            cin >> x;
            new_tree[x]++;
        }
        ans = n-1+d+def_ans;
        int not_l = 0l;
        verts_pom = {};
        forall(it,new_tree)
        {
            if(siz(graph[it.ff]) == 1) 
            {
                new_tree[it.ff]--;
                not_l++;
            }
            if(new_tree[it.ff] % 2 == 1) verts_pom.pb({pre[it.ff],it.ff});
        }
        sort(all(verts_pom));
        if((total_leafs + d - not_l) % 2 == 1)
        {
            cout << "-1\n";
            continue;
        }
        if(siz(verts_pom) == 0)
        {
            cout << ans << "\n";
            continue;
        }
        new_tree = {};
        forall(it,verts_pom) new_tree[it.ss] = 1;
        int prev = -1;
        forall(it,verts_pom)
        {
            is_change[it.ss] = 1;
            if(prev != -1)
            {
                new_tree[lca(prev,it.ss)] = 1;
            }
            prev = it.ss;
        }
        new_tree[lca(verts_pom[0].ss,prev)] = 1;
        verts_pom = {};
        forall(it,new_tree) verts_pom.pb({-depth[it.ff],it.ff});
        sort(all(verts_pom));
        int root2 = 0;
        new_sons = {};
        forall(it,verts_pom)
        {
            auto ptr = new_sons.lower_bound({pre[it.ss],-1});
            root2 = it.ss;
            while(ptr != new_sons.end())
            {
                if((*ptr).ff <= max_pre[it.ss])
                {
                    sons[it.ss].pb((*ptr).ss);
                    new_sons.erase(ptr);
                    ptr = new_sons.lower_bound({pre[it.ss],-1});
                }
                else
                {
                    break;
                }
            }
            new_sons.insert({pre[it.ss],it.ss});
        }
        dfs_ans(root2,root);
        cout << ans << "\n";
        forall(it,verts_pom)
        {
            is_change[it.ss] = 0;
            sons[it.ss] = {};
        }
    }
}

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