Submission #1080820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080820		RecursiveCo	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	127 ms	35280 KiB

cleaning

// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long int

template <typename T, typename I>
struct segtree {
    int n;
    vector<T> tree;
    vector<I> initial;
    T id;

    segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) {
        tree.resize(4 * n);
    }

    T conquer(T left, T right) {
        // write your conquer function
    }

    T value(I inp) {
        // write your value function
    }

    void build(int v, int l, int r) {
        if (l == r) tree[v] = value(initial[l]);
        else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int v, int l, int r, int i, I x) {
        if (l == r) tree[v] = value(x);
        else {
            int middle = (l + r) / 2;
            if (middle >= i) upd(2 * v, l, middle, i, x);
            else upd(2 * v + 1, middle + 1, r, i, x);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    T query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        else if (r < ql || qr < l) return id;
        int middle = (l + r) / 2;
        T left = query(2 * v, l, middle, ql, qr);
        T right = query(2 * v + 1, middle + 1, r, ql, qr);
        return conquer(left, right);
    }
};

// vector<int>

// I'm practising virtual trees. I thought of the hld solution myself but yk I really cba to implement it
// so I read the editorial and I found the cool virtual trees solution. Time to practise it
// ~~and get lost in implementation hell for an hour or ten~~

vector<vector<int>> adjList;
vector<int> parity;
vector<int> height;
vector<int> upto;
vector<int> tin;
vector<int> tout;
vector<vector<int>> lift;
int tot = 0;
int timer = 0;
int root;

void dfs1(int v, int p, int h) {
    tin[v] = timer++;
    height[v] = h;
    lift[v][0] = p == -1? v: p;
    forto(18, i) {
        if (i == 0) continue;
        lift[v][i] = lift[lift[v][i - 1]][i - 1];
    }
    for (int con: adjList[v]) {
        if (con == p) continue;
        dfs1(con, v, h + 1);
        if (parity[con] == 0) parity[v] = 1 - parity[v];
    }
    if (adjList[v].size() == 1) parity[v] = 1 - parity[v];
    tout[v] = timer;
}

void dfs2(int v, int p, int sum) {
    sum += parity[v];
    tot += parity[v];
    upto[v] = sum;
    for (int con: adjList[v]) {
        if (con == p) continue;
        dfs2(con, v, sum);
    }
}

int lca(int u, int v) {
    if (height[u] > height[v]) swap(u, v);
    int dif = height[v] - height[u];
    int p = 1;
    forto(18, i) {
        if (dif & p) v = lift[v][i];
        p *= 2;
    }
    // now they're the same height
    if (u == v) return u; // = v
    for (int i = 17; i >= 0; i--) {
        int x = lift[u][i];
        int y = lift[v][i];
        if (x != y) {
            u = x;
            v = y;
        }
    }
    return lift[u][0];
}

int dfs3(int v, int p, vector<int>& actnodes, vector<vector<int>>& tree, vector<bool>& isflip) {
    int here = isflip[v];
    for (int con: tree[v]) {
        here += dfs3(con, v, actnodes, tree, isflip);
    }
    if (here % 2) {
        int parent = p == -1? root: actnodes[p];
        int length = height[actnodes[v]] - height[parent];
        int sum = upto[actnodes[v]] - upto[parent];
        if (p == -1) {
            length++;
            sum += parity[root];
        }
        tot += length - 2 * sum;
    }
    return here;
}

signed main() {
    improvePerformance;
    //getTest;
    
    //eachTest {
        get(n);
        get(q);
        adjList.resize(n);
        parity.resize(n, 1);
        height.resize(n);
        upto.resize(n);
        tin.resize(n);
        tout.resize(n);
        lift.resize(n, vector<int>(18));
        forto(n - 1, i) {
            get(a);
            get(b);
            a--;
            b--;
            adjList[a].push_back(b);
            adjList[b].push_back(a);
        }
        forto(n, i) {
            if (adjList[i].size() != 1) {
                dfs1(i, -1, 1);
                dfs2(i, -1, 0);
                root = i;
                break;
            }
        }
        bool evenleaves = parity[root] == 1;
        int original = tot;
        forto(q, i) {
            get(d);
            map<int, int> cnt;
            // We need to figure out which nodes get their parity flipped.
            int m = n;
            forto(d, j) {
                get(x);
                x--;
                cnt[x]++;
                m++;
            }
            bool works = evenleaves;
            vector<pair<int, int>> flip;
            for (auto it = cnt.begin(); it != cnt.end(); it++) {
                int v = it->first;
                int c = it->second;
                if (adjList[v].size() == 1) c++;
                if (c % 2) flip.push_back({tin[v], v}), works = !works;
            }
            sortl(flip);
            set<pair<int, int>> nodes;
            set<pair<int, int>> flipnodes;
            for (pair<int, int> node: flip) nodes.insert(node), flipnodes.insert(node);
            int length = flip.size();
            forto(length - 1, i) {
                int here = lca(flip[i].second, flip[i + 1].second);
                nodes.insert({tin[here], here});
            }
            vector<int> actnodes;
            for (auto it = nodes.begin(); it != nodes.end(); it++) actnodes.push_back((*it).second);
            int k = actnodes.size();
            vector<vector<int>> tree(k);
            vector<bool> isflip;
            stack<int> st;
            int j = 0;
            for (int v: actnodes) {
                while (!st.empty()) {
                    int l = st.top();
                    int u = actnodes[l];
                    if (tin[u] < tin[v] && tout[v] <= tout[u]) break;
                    st.pop();
                }
                if (!st.empty()) {
                    int l = st.top();
                    tree[l].push_back(j);
                }
                isflip.push_back(flipnodes.find({tin[v], v}) != flipnodes.end());
                st.push(j);
                j++;
            }
            if (k) dfs3(0, -1, actnodes, tree, isflip);
            if (works) out(m - 2 + tot);
            else out(-1);
            out("\n");
            tot = original;
        }
    //}
}

Compilation message (stderr)

cleaning.cpp: In function 'void dfs1(int, int, int)':
cleaning.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
cleaning.cpp:90:5: note: in expansion of macro 'forto'
   90 |     forto(18, i) {
      |     ^~~~~
cleaning.cpp: In function 'int lca(int, int)':
cleaning.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
cleaning.cpp:117:5: note: in expansion of macro 'forto'
  117 |     forto(18, i) {
      |     ^~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
cleaning.cpp:157:9: note: in expansion of macro 'get'
  157 |         get(n);
      |         ^~~
cleaning.cpp:10:23: warning: unnecessary parentheses in declaration of 'q' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
cleaning.cpp:158:9: note: in expansion of macro 'get'
  158 |         get(q);
      |         ^~~
cleaning.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
cleaning.cpp:166:9: note: in expansion of macro 'forto'
  166 |         forto(n - 1, i) {
      |         ^~~~~
cleaning.cpp:10:23: warning: unnecessary parentheses in declaration of 'a' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
cleaning.cpp:167:13: note: in expansion of macro 'get'
  167 |             get(a);
      |             ^~~
cleaning.cpp:10:23: warning: unnecessary parentheses in declaration of 'b' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
cleaning.cpp:168:13: note: in expansion of macro 'get'
  168 |             get(b);
      |             ^~~
cleaning.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
cleaning.cpp:174:9: note: in expansion of macro 'forto'
  174 |         forto(n, i) {
      |         ^~~~~
cleaning.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
cleaning.cpp:184:9: note: in expansion of macro 'forto'
  184 |         forto(q, i) {
      |         ^~~~~
cleaning.cpp:10:23: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
cleaning.cpp:185:13: note: in expansion of macro 'get'
  185 |             get(d);
      |             ^~~
cleaning.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
cleaning.cpp:189:13: note: in expansion of macro 'forto'
  189 |             forto(d, j) {
      |             ^~~~~
cleaning.cpp:10:23: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
cleaning.cpp:190:17: note: in expansion of macro 'get'
  190 |                 get(x);
      |                 ^~~
cleaning.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
cleaning.cpp:208:13: note: in expansion of macro 'forto'
  208 |             forto(length - 1, i) {
      |             ^~~~~

• 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