Submission #290094

#	Time	Username	Problem	Language	Result	Execution time	Memory
290094		model_code	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	261 ms	32372 KiB

cleaning

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

/*
LCA solution, it works when you don't know the ith question before answering the i-1th
Note that this is an O(NlogN) solution

Made for you by Mate Busa
*/

int N, Q, a, b, cur, num, o, ans, root, dif, last, level, oo;
vector<int> neighbour[200000];
bool visited[200000];
int dis[200000];
int parent[200000];
int order[200000][2];
int number[200000];
int dp[200000];
int fia[200000];
int f[200000];
vector<int> d[200000];
set<int> reuse;
set<int> who;
vector<int> vec;

void dfs(int x){
    visited[x] = true; order[x][0] = cur++; oo++;
    if(root==x){
        parent[x] = -1;
    } else {
        int hat = 0; while((1<<hat)<=dis[x]) hat++;
        d[x].resize(hat); d[x][0] = parent[x];
        for(int i=1; i<hat; i++) d[x][i] = d[d[x][i-1]][i-1];
    }
    bool lv = true;
    for(int i:neighbour[x]){
        if(!visited[i]){
            dis[i] = dis[x]+1; parent[i] = x;
            dfs(i); lv = false; dp[x] += dp[i];
        }
    }
    if(lv) dp[x]++;
    if(dp[x]%2==0) o++;
    order[x][1] = cur++;
}
void pre(int x){
    for(int i:neighbour[x]){
        if(parent[x]!=i){
            dp[i] = dp[i]%2 + dp[x];
            pre(i);
        }
    }
}
int lca(int x, int y){
    if(dis[y]<dis[x]) swap(x,y);
    for(int i=d[y].size()-1; dis[x]!=dis[y]; i--){
        if(dis[y]-(1<<i)>=dis[x]) y = d[y][i];
    }
    if(x==y) return x;
    for(int i=d[x].size()-1; parent[x]!=parent[y]; i--){
        if((1<<i)<=dis[x] && d[x][i]!=d[y][i]){x = d[x][i]; y = d[y][i];}
    }
    return parent[x];
}

bool smaller(int x, int y){
    return order[x][dif] < order[y][dif];
}

int calc(int x){
    return (dp[x]-(dis[x]+1-dp[x]));
}
///find parent in LCA tree
void up(){
    if(number[a]%2==1){
        ans += calc(a);
        if(f[a]!=-1)  ans -= calc(f[a]);
    }
    if(f[a]!=-1) number[f[a]] += number[a];
    a = f[a];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    cin >> N >> Q;
    for(int i=0; i<N-1; i++){
        cin >> a >> b;
        neighbour[a-1].push_back(b-1);
        neighbour[b-1].push_back(a-1);
    }
    ///find an inside point
    for(int i=0; i<N; i++) if(neighbour[i].size()!=1) {root = i; break;}

    dfs(root); level = dp[root];
    dp[root] %= 2; pre(root);

    for(int ii=0; ii<Q; ii++){
        reuse.clear(); vec.clear(); who.clear(); ans = N-1+o;
        cin >> num; ans += num;
        for(int i=0; i<num; i++){
            cin >> a; number[a-1]++; reuse.insert(a-1);
        }
        for(int i:reuse){
            if((neighbour[i].size()==1 && number[i]>=2 && number[i]%2==0) || (neighbour[i].size()>1 && number[i]%2==1)){
                vec.push_back(i); number[i] = 1;
            } else {
                number[i] = 0;
            }
        }
        if((level+vec.size())%2==1){
            cout << -1 << '\n';
            for(int i:vec) number[i] = 0;
        } else {
            if(vec.size()!=0){
                dif = 1; sort(vec.begin(),vec.end(),smaller);
                last = -1;
                for(int i:vec){
                    who.insert(i);
                    if(last!=-1) who.insert(lca(last,i));
                    last = i;
                }
                cur = 0;
                for(int i:who) fia[cur++] = i;
                dif = 0; sort(fia,fia+cur,smaller);
                f[fia[0]] = -1; a = fia[0];
                for(int i=1; i<cur; i++){
                    while(order[a][1]<order[fia[i]][0]) up();
                    f[fia[i]] = a; a = fia[i];
                }
                while(a!=-1) up();
                for(int i=0; i<cur; i++) number[fia[i]] = 0;
            }
            cout << ans-1 << '\n';
        }
    }

    return 0;
}

• 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