oj.uz

Submission #952868

# Submission time Handle Problem Language Result Execution time Memory
952868 2024-03-25T03:43:45 Z GrindMachine Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 307 ms 42596 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
 
template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}
 
template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
 
/*
 
 
 
*/
 
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];

struct lca_algo {
    // LCA template (for graphs with 1-based indexing)
 
    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;
    vector<int> tin, tout;
    int timer = 1;
 
    lca_algo() {
 
    }
 
    lca_algo(int n, int r) {
        lca_init(n,r);
    }
 
    void lca_init(int n, int r) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, r));
        depth = vector<int>(n + 1);
        tin = vector<int>(n + 1);
        tout = vector<int>(n + 1);
 
        lca_dfs(r, -1);
    }
 
    void lca_dfs(int node, int par) {
        tin[node] = timer++;
 
        trav(child, adj[node]) {
            if (child == par) conts;
 
            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }
 
            depth[child] = depth[node] + 1;
 
            lca_dfs(child, node);
        }
 
        tout[node] = timer-1;
    }
 
    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }
 
        return u;
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);
 
        if (u == v) return u;
 
        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
 
        u = up[u][0];
        return u;
    }
 
    int get_dis(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }
 
    bool is_ances(int u, int v){
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }
};

vector<ll> depth(N);
vector<ll> leaves(N);
vector<ll> dp(N);
vector<bool> leaf(N);
vector<ll> leaf_sum(N);

void dfs1(ll u, ll p){
    leaves[u] = 0;
 
    ll children = 0;
 
    trav(v,adj[u]){
        if(v == p) conts;
        depth[v] = depth[u]+1;
        dfs1(v,u);
        children++;
    }
 
    if(!children){
        leaves[u] = leaf[u] = leaf_sum[u] = 1;
        return;
    }
 
    trav(v,adj[u]){
        if(v == p) conts;
        leaves[u] += leaves[v];
    }
    
    leaf_sum[u] = leaves[u];

    if(leaves[u]){
        if(leaves[u]&1){
            dp[u] = depth[u]*(leaves[u]>>1);
            leaves[u] = 1;
        }
        else{
            dp[u] = depth[u]*((leaves[u]-2)>>1);
            leaves[u] = 2;
        }
    }
}

ll parity_sum[N][3][3];

void dfs2(ll u, ll p){
    if(p != -1){
        parity_sum[u][leaves[u]][leaves[p]] = depth[p];
        rep1(j,2){
            rep1(k,2){
                parity_sum[u][j][k] += parity_sum[p][j][k];
            }
        }
    }

    trav(v,adj[u]){
        if(v == p) conts;
        dfs2(v,u);
    }
}

vector<ll> adj2[N];

void solve(int test_case)
{
    ll n,q; cin >> n >> q;
    rep1(i,n-1){
        ll u,v; cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }
 
    ll root = -1;
    rep1(i,n){
        if(sz(adj[i]) >= 2){
            root = i;
        }
    }

    dfs1(root,-1);
    dfs2(root,-1);
    lca_algo LCA(n,root);

    ll depth_sum = 0;
    rep1(i,n) depth_sum += depth[i]*leaf[i];

    ll leaf_cnt = 0;
    rep1(i,n) leaf_cnt += leaf[i];

    ll sub = 0;
    rep1(i,n) sub += dp[i];

    vector<ll> curr_leaves(n+5);
    rep1(i,n) curr_leaves[i] = leaf_sum[i];

    vector<bool> is_leaf(n+5);
    rep1(i,n) is_leaf[i] = leaf[i];

    debug(root);

    while(q--){
        ll k; cin >> k;
        vector<pll> b(k);
        ll curr_depth_sum = depth_sum;
        ll curr_leaf_cnt = leaf_cnt;
        ll curr_sub = sub;

        rep(i,k){
            ll u; cin >> u;
            b[i] = {LCA.tin[u],u};
            curr_leaf_cnt++;
            curr_depth_sum += depth[u]+1;
            if(is_leaf[u]){
                is_leaf[u] = 0;
                curr_leaves[u] = 0;
                curr_leaf_cnt--;
                curr_depth_sum -= depth[u];
            }
            curr_leaves[u]++;
        }

        sort(all(b));
        rep(i,k-1){
            ll u = b[i].ss, v = b[i+1].ss;
            ll lca = LCA.query(u,v);
            b.pb({LCA.tin[lca],lca});
        }
        b.pb({LCA.tin[root],root});

        sort(all(b));
        b.resize(unique(all(b))-b.begin());
        ll siz = sz(b);
        vector<ll> par(siz);

        stack<ll> stk;
        rep(i,siz){
            ll u = b[i].ss;
            while(!stk.empty() and !LCA.is_ances(stk.top(),u)){
                stk.pop();
            }

            if(i){
                par[i] = stk.top();
                adj2[par[i]].pb(u);
            }

            stk.push(u);
        }

        rev(i,siz-1,0){
            ll u = b[i].ss, p = par[i];
            trav(v,adj2[u]){
                if(curr_leaves[v] != leaves[v]){
                    ll just_below = LCA.lift(v,depth[v]-depth[u]-1);
                    curr_leaves[u] -= leaves[just_below];
                    curr_leaves[u] += 3^leaves[just_below]; 
                }
            }

            curr_sub -= dp[u];

            if(curr_leaves[u]&1){
                curr_sub += depth[u]*(curr_leaves[u]>>1);
                curr_leaves[u] = 1;
            }
            else{
                curr_sub += depth[u]*((curr_leaves[u]-2)>>1);
                curr_leaves[u] = 2;
            }

            if(i and leaves[u] != curr_leaves[u]){
                ll p = par[i];
                ll just_below = LCA.lift(u,depth[u]-depth[p]-1);
                ll sum1 = parity_sum[u][1][2]-parity_sum[just_below][1][2];
                ll sum2 = parity_sum[u][2][1]-parity_sum[just_below][2][1];
                curr_sub += sum1-sum2;
            }
        }

        debug(curr_depth_sum);

        ll ans = curr_depth_sum-curr_sub*2;
        if(curr_leaf_cnt&1) ans = -1;
        cout << ans << endl;

        for(auto [ti,u] : b){
            curr_leaves[u] = leaf_sum[u];
            is_leaf[u] = leaf[u];
            adj2[u].clear();
        }
    }
}
 
int main()
{
    fastio;
 
    int t = 1;
    // cin >> t;
 
    rep1(i, t) {
        solve(i);
    }
 
    return 0;
}

Compilation message

cleaning.cpp: In function 'void dfs1(ll, ll)':
cleaning.cpp:165:43: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  165 |         leaves[u] = leaf[u] = leaf_sum[u] = 1;
cleaning.cpp: In function 'void solve(int)':
cleaning.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define debug(x) 42
      |                  ^~
cleaning.cpp:242:5: note: in expansion of macro 'debug'
  242 |     debug(root);
      |     ^~~~~
cleaning.cpp:294:29: warning: unused variable 'p' [-Wunused-variable]
  294 |             ll u = b[i].ss, p = par[i];
      |                             ^
cleaning.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define debug(x) 42
      |                  ^~
cleaning.cpp:323:9: note: in expansion of macro 'debug'
  323 |         debug(curr_depth_sum);
      |         ^~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 58 ms 15420 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 11908 KB Output is correct
2 Correct 29 ms 11896 KB Output is correct
3 Correct 73 ms 32316 KB Output is correct
4 Correct 67 ms 29180 KB Output is correct
5 Correct 123 ms 36536 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15472 KB Output is correct
2 Correct 31 ms 12664 KB Output is correct
3 Correct 72 ms 38992 KB Output is correct
4 Correct 93 ms 41844 KB Output is correct
5 Correct 55 ms 36836 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 14164 KB Output is correct
2 Correct 25 ms 14940 KB Output is correct
3 Correct 20 ms 13104 KB Output is correct
4 Correct 22 ms 14940 KB Output is correct
5 Correct 15 ms 13660 KB Output is correct
6 Correct 42 ms 14420 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25940 KB Output is correct
2 Correct 128 ms 25980 KB Output is correct
3 Correct 71 ms 17144 KB Output is correct
4 Correct 109 ms 26128 KB Output is correct
5 Correct 151 ms 25988 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 33264 KB Output is correct
2 Correct 178 ms 36432 KB Output is correct
3 Correct 182 ms 34812 KB Output is correct
4 Correct 157 ms 35208 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 58 ms 15420 KB Output is correct
3 Correct 21 ms 11908 KB Output is correct
4 Correct 29 ms 11896 KB Output is correct
5 Correct 73 ms 32316 KB Output is correct
6 Correct 67 ms 29180 KB Output is correct
7 Correct 123 ms 36536 KB Output is correct
8 Correct 30 ms 15472 KB Output is correct
9 Correct 31 ms 12664 KB Output is correct
10 Correct 72 ms 38992 KB Output is correct
11 Correct 93 ms 41844 KB Output is correct
12 Correct 55 ms 36836 KB Output is correct
13 Correct 63 ms 14164 KB Output is correct
14 Correct 25 ms 14940 KB Output is correct
15 Correct 20 ms 13104 KB Output is correct
16 Correct 22 ms 14940 KB Output is correct
17 Correct 15 ms 13660 KB Output is correct
18 Correct 42 ms 14420 KB Output is correct
19 Correct 75 ms 25940 KB Output is correct
20 Correct 128 ms 25980 KB Output is correct
21 Correct 71 ms 17144 KB Output is correct
22 Correct 109 ms 26128 KB Output is correct
23 Correct 151 ms 25988 KB Output is correct
24 Correct 138 ms 33264 KB Output is correct
25 Correct 178 ms 36432 KB Output is correct
26 Correct 182 ms 34812 KB Output is correct
27 Correct 157 ms 35208 KB Output is correct
28 Correct 90 ms 24420 KB Output is correct
29 Correct 170 ms 35532 KB Output is correct
30 Correct 94 ms 36484 KB Output is correct
31 Correct 95 ms 42596 KB Output is correct
32 Correct 148 ms 26496 KB Output is correct
33 Correct 147 ms 31724 KB Output is correct
34 Correct 307 ms 35316 KB Output is correct
35 Correct 296 ms 36372 KB Output is correct