Submission #1046679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046679		beaconmc	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	176 ms	69884 KiB

cleaning

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
 
vector<ll> edges[200005];
vector<ll> vtree[200005];
ll realans = 0;
ll vals[200005];
ll contrib[200005];
ll depth[200005];
ll par[200005];
ll tin[200005];
ll timer = 0;
map<ll, ll> lmao;

ll lmfao = 0;
 
ll dp(ll a, ll p){
    tin[a] = timer++;
    par[a] = p;
    ll ans = 0;
    if (edges[a].size() <= 1) ans = 1;
    for (auto&i : edges[a]){
        if (i != p) ans += dp(i, a);
    }       
    if (p!=-1) realans += 1 + (ans+1)%2;
 
    if (p != -1) vals[a] = 1 + (ans+1)%2;

    return 1 + (ans+1)%2;
}
void dp2(ll a, ll p, ll d){


    depth[a] = d;

    if (p==-1) contrib[a] = 0;
    if (p != -1){
        contrib[a] = contrib[par[a]] + vals[a]; 
    }


    for (auto&i : edges[a]){
        if (i != p) dp2(i, a, d+1);
        
    }

}
ll dp3(ll a, ll p){

    ll tot = lmao[a];

    for (auto&i : vtree[a]){
        tot += dp3(i,a);
    }
    if (depth[a]==0) return 0;
    lmfao += (tot/2)*2 * -(depth[a]*3 - contrib[a]*2);
    return (tot)%2;
}

int anc[200005][30];

int ancc(ll a, ll x){

    if (par[a] == -1) return a;

    if (x==0) return par[a];

    if (anc[a][x] != -1) return anc[a][x];

    else{
        return anc[a][x] = ancc(ancc(a,x-1),x-1);
    }
}

ll lca(ll a, ll b){
    if (depth[a] < depth[b]) swap(a,b);


    FORNEG(i,29,-1) if (depth[ancc(a, i)] >= depth[b]) a = ancc(a,i);

    if (a==b) return a;

    FORNEG(i,29,-1) if (ancc(a,i) != ancc(b,i)) a = ancc(a,i), b = ancc(b,i);
    return par[a];
}

int main(){
    FOR(i,0,200005) FOR(j,0,30) anc[i][j] = -1;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,q;
    cin >> n >> q;
    FOR(i,0,n-1){
        ll a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    ll root = -1;
    ll cnt = 0;
    FOR(j,1,n+1){
        if (edges[j].size() != 1){
            root = j;
        }else{
            cnt++;
        }
    }

    dp(root, -1);
    dp2(root, -1, 0);



    ll ans = 0;
    FOR(i,1,n+1) ans += vals[i];
    
 
    FOR(i,0,q){
        ll d; cin >> d;
        ll cur = n+1;
        ll curans = 0;
        set<ll> used;
        ll newleaves=0;
        lmao.clear();
        vector<vector<ll>> stuff;
        lmfao = 0;
        

        FOR(k,0,d){
            ll temp; cin >> temp;
            used.insert(temp);
            curans++;
            edges[temp].push_back(cur++);
            if (edges[temp].size() == 2)continue;

            newleaves++;
            stuff.push_back({tin[temp], temp});
            curans += depth[temp]*3 - contrib[temp]*2;
            lmao[temp] += 1;
        }

        sort(stuff.begin(), stuff.end());
        set<vector<ll>> stuff2;
        FOR(i,1,stuff.size()){
            ll lcatemp = lca(stuff[i][1], stuff[i-1][1]);

            stuff2.insert({tin[lcatemp], lcatemp});
        }


        if (stuff.size()){
                ll lcatemp = lca(stuff[0][1], stuff[stuff.size()-1][1]);
                stuff2.insert({tin[lcatemp], lcatemp});

            for (auto&i : stuff)stuff2.insert(i);

            ll virtualroot = (*(stuff2.begin()))[1];
            vector<ll> stack;
            for (auto&k : stuff2){
                while (stack.size() && lca(stack[stack.size()-1], k[1]) != stack[stack.size()-1]) stack.pop_back();
                if (stack.size()) vtree[stack[stack.size()-1]].push_back(k[1]);
                stack.push_back(k[1]);
            }


            dp3(virtualroot, -1);

        }


        if ((cnt+newleaves)%2==1) cout << -1 << "\n";
        else{
            cout << ans+curans+lmfao << "\n";
        }
        for (auto&i : stuff2) vtree[i[1]].clear();
        for (auto&i : used){
            while (edges[i].size() && edges[i][edges[i].size()-1]>n){
                edges[i].pop_back();
            }
        }
 
    }

}
 
 
 
 
 

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:4:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  149 |         FOR(i,1,stuff.size()){
      |             ~~~~~~~~~~~~~~~~     
cleaning.cpp:149:9: note: in expansion of macro 'FOR'
  149 |         FOR(i,1,stuff.size()){
      |         ^~~

• 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