oj.uz

Submission #956316

# Submission time Handle Problem Language Result Execution time Memory
956316 2024-04-01T15:07:00 Z thangdz2k7 Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 187 ms 49932 KB 
// author : HuuHung
// 25.3.2024


#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
#define ll long long
#define lb long double
#define pb push_back
#define vi vector <int>
#define vll vector <ll>
#define Bit(x, i) ((x) >> (i) & 1)
#define Mask(i) (1ll << (i))
#define All(v) (v).begin(), (v).end()

using namespace std;

void maxzi(int &a, int b){
    a = max(a, b);
}

void minzi(int &a, int b){
    a = min(a, b);
}

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int Pow(int a, int b){
    if (b == 0) return 1;
    if (b % 2) return 1ll * a * Pow(a, b - 1) % mod;
    int c = Pow(a, b / 2);
    return 1ll * c * c % mod;
}

// * end

int deg[N], num[N];
vector <int> s;
vector <int> nw[N];

struct LCA{
    vi st, ed, _lg, high, type, num[2];
    vector <vi> euler, adj;
    int cnt, ans, root, leaf;

    void dfs1(int u, int pa){
        ++ cnt;
        st[u] = cnt;
        euler[cnt].pb(u);
        if (deg[u] == 1) type[u] = 1, leaf ++;
        for (int v : adj[u]){
            if (v == pa) continue;
            high[v] = high[u] + 1;
            dfs1(v, u);
            euler[++ cnt].pb(u);
            type[u] ^= type[v];
        }
        ed[u] = cnt;
    }

    int check(int u, int v) {
        return st[u] <= st[v] && ed[v] <= ed[u];
    }

    int min_by_time(int u, int v) {
        return (st[u] < st[v] ? u : v);
    }

    void added(int u, int v){
        adj[u].pb(v);
        adj[v].pb(u);
    }

    void resize(int n){
        leaf = 0;
        ans = n - 1;
        st.resize(n + 3, 0);
        ed.resize(n + 3, 0);
        euler.resize(2 * n + 5);
        high.resize(n + 3, 0);
        type.resize(n + 3, 0);
        num[0].resize(n + 3, 0);
        num[1].resize(n + 3, 0);
        adj.resize(n + 3);
        _lg.resize(2 * n + 5);
        for (int i = 0; i <= 2 * n; ++ i) _lg[i] = log2(i);
    }

    void dfs2(int u, int pa){
        for (int v : adj[u]){
            if (v == pa) continue;
            num[0][v] = num[0][u];
            num[1][v] = num[1][u];
            num[type[v]][v] ++;
            ans += (type[v] ^ 1);
            dfs2(v, u);
        }
    }

    void init(int r){
        root = r;
        cnt = 0;
        high[r] = 1;
        dfs1(r, 0);
        for (int lg = 1; lg < 20; ++lg) {
            for (int i = 1; i + (1 << lg) - 1 <= cnt; ++i)
                euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
        }
        dfs2(r, 0);
    }

    int get(int u, int v) {
        int L = min(st[u], st[v]);
        int R = max(ed[u], ed[v]);
        int lg = _lg[R - L + 1];
        return min_by_time(euler[L][lg], euler[R - (1 << lg) + 1][lg]);
    }

    int dist(int t, int u, int pa){ return num[t][u] - num[t][pa]; }
} tree;

vector <int> cur;

int process(){
    int ans = tree.ans;
    sort(s.begin(), s.end(), [&](int u, int v){
       return tree.st[u] < tree.st[v];
    });

    int m = s.size();
    for (int i = 1; i < m; ++ i) s.push_back(tree.get(s[i], s[i - 1]));
    s.pb(tree.root);
    sort(s.begin(), s.end(), [&](int u, int v) {
        return tree.st[u] < tree.st[v];
    });
    s.erase(unique(s.begin(), s.end()), s.end());
    reverse(s.begin(), s.end());

    vector <int> stk;
    for (auto u : s){
        while (stk.size() && tree.check(u, stk.back())) {
            int v = stk.back();
            stk.pop_back();
            nw[u].push_back(v);
        }
        stk.push_back(u);
    }

    function <void (int, int)> dfs = [&](int u, int pa){
        for (int v : nw[u]){
            if (v == pa) continue;
            dfs(v, u);
            num[u] ^= num[v];
        }
        if (num[u]) ans += (-tree.dist(0, u, pa) + tree.dist(1, u, pa));
    };

    dfs(tree.root, tree.root);

    for (int u : s) nw[u].clear();
    return ans;
}

void solve(){
    int n, q;
    cin >> n >> q;
    tree.resize(n);
    int root = 1;
    for (int i = 1, u, v; i < n; ++ i){
        cin >> u >> v;
        tree.added(u, v);
        deg[u] ++;
        deg[v] ++;
        if (deg[u] > 1) root = u;
        if (deg[v] > 1) root = v;
    }
    tree.init(root);

    while (q --){
        for (int v : s) num[v] = 0;
        s.clear();
        //vector <int> cur;
        int d; cin >> d;
        for (int i = 1; i <= d; ++ i){
            int a; cin >> a;
            if (!num[a]) cur.pb(a);
            //cout << a << endl;
            num[a] ++;
        }
        int no = 0;
        for (int v : cur){
            num[v] %= 2;
            if ((num[v] && deg[v] > 1) || (!num[v] && deg[v] == 1)) num[v] = 1, s.pb(v);
            if (deg[v] == 1) no ++;
        }
        //cout << no << endl;
        if ((tree.leaf - no + d) % 2) cout << -1 << '\n';
        else cout << process() + d << '\n';
        for (int v : cur) num[v] = 0;
        cur.clear();
    }
}


int main(){
    //freopen("spring.inp", "r", stdin);
    //freopen("spring.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t --) solve();

    return 0;
}

Compilation message

cleaning.cpp: In member function 'void LCA::init(int)':
cleaning.cpp:117:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  117 |                 euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
      |                                                                           ~~~^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 33 ms 11084 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5980 KB Output is correct
2 Correct 8 ms 5980 KB Output is correct
3 Correct 98 ms 43608 KB Output is correct
4 Correct 72 ms 31432 KB Output is correct
5 Correct 122 ms 44216 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7004 KB Output is correct
2 Correct 9 ms 6748 KB Output is correct
3 Correct 110 ms 48024 KB Output is correct
4 Correct 120 ms 45928 KB Output is correct
5 Correct 99 ms 44056 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12112 KB Output is correct
2 Correct 24 ms 11752 KB Output is correct
3 Correct 18 ms 11356 KB Output is correct
4 Correct 18 ms 12124 KB Output is correct
5 Correct 19 ms 12012 KB Output is correct
6 Correct 29 ms 12424 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 29428 KB Output is correct
2 Correct 88 ms 28936 KB Output is correct
3 Correct 44 ms 15936 KB Output is correct
4 Correct 94 ms 30212 KB Output is correct
5 Correct 96 ms 30548 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 43896 KB Output is correct
2 Correct 187 ms 47508 KB Output is correct
3 Correct 165 ms 47176 KB Output is correct
4 Correct 134 ms 45916 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 33 ms 11084 KB Output is correct
3 Correct 8 ms 5980 KB Output is correct
4 Correct 8 ms 5980 KB Output is correct
5 Correct 98 ms 43608 KB Output is correct
6 Correct 72 ms 31432 KB Output is correct
7 Correct 122 ms 44216 KB Output is correct
8 Correct 10 ms 7004 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 110 ms 48024 KB Output is correct
11 Correct 120 ms 45928 KB Output is correct
12 Correct 99 ms 44056 KB Output is correct
13 Correct 38 ms 12112 KB Output is correct
14 Correct 24 ms 11752 KB Output is correct
15 Correct 18 ms 11356 KB Output is correct
16 Correct 18 ms 12124 KB Output is correct
17 Correct 19 ms 12012 KB Output is correct
18 Correct 29 ms 12424 KB Output is correct
19 Correct 84 ms 29428 KB Output is correct
20 Correct 88 ms 28936 KB Output is correct
21 Correct 44 ms 15936 KB Output is correct
22 Correct 94 ms 30212 KB Output is correct
23 Correct 96 ms 30548 KB Output is correct
24 Correct 139 ms 43896 KB Output is correct
25 Correct 187 ms 47508 KB Output is correct
26 Correct 165 ms 47176 KB Output is correct
27 Correct 134 ms 45916 KB Output is correct
28 Correct 82 ms 27732 KB Output is correct
29 Correct 133 ms 48876 KB Output is correct
30 Correct 120 ms 45500 KB Output is correct
31 Correct 120 ms 47464 KB Output is correct
32 Correct 87 ms 30288 KB Output is correct
33 Correct 123 ms 40152 KB Output is correct
34 Correct 152 ms 48452 KB Output is correct
35 Correct 173 ms 49932 KB Output is correct