Submission #381964

#	Time	Username	Problem	Language	Result	Execution time	Memory
381964		jainbot27	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	449 ms	29228 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

//use to make shit go faster (magic from KACTL)
//static char buf[450 << 20];
//void* operator new(size_t s) {
//    static size_t i = sizeof buf;
//    assert(s < i);
//    return (void*)&buf[i -= s];
//}
//void operator delete(void*) {}

// implicit lazy segment tree adapted from KACTL
template<class V> struct Node {
    Node *l = 0, *r = 0;
    const V no_op = 0;
    int lo, hi; V mset = no_op, val = 0;
    Node(int lo,int hi):lo(lo),hi(hi){} 
    Node(vector<V>& v, int lo, int hi) : lo(lo), hi(hi) {
        if (lo + 1 < hi) {
            int mid = lo + (hi - lo)/2;
            l = new Node(v, lo, mid); r = new Node(v, mid, hi);
            val = l->val+r->val;
        }
        else val = v[lo];
    }
    V query(int L, int R) {
        if (R <= lo || hi <= L) return 0;
        if (L <= lo && hi <= R) return val;
        push();
        return l->query(L, R)+r->query(L, R);
    }
    void set(int L, int R, V x) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) {
            val = (hi-lo)-val; mset ^= x; 
        }
        else {
            push(), l->set(L, R, x), r->set(L, R, x);
            val = l->val+r->val;
        }
    }
    void push() {
        if (!l) {
            int mid = lo + (hi - lo)/2;
            l = new Node(lo, mid); r = new Node(mid, hi);
        }
        if(mset!=no_op)
            l->set(lo,hi,mset), r->set(lo,hi,mset), mset = no_op;
    }
};

template <bool VALS_EDGES> struct HLD {
	int N, tim = 0;
	vector<vi> adj;
	vi par, siz, depth, rt, pos;
	Node<int> *tree;
	HLD(vector<vi> adj_)
		: N(sz(adj_)), adj(adj_), par(N, -1), siz(N, 1), depth(N),
		  rt(N),pos(N),tree(new Node<int>(0, N)){ dfsSz(0); dfsHld(0); }
	void dfsSz(int v) {
		if (par[v] != -1) adj[v].erase(find(all(adj[v]), par[v]));
		for (int& u : adj[v]) {
			par[u] = v, depth[u] = depth[v] + 1;
			dfsSz(u);
			siz[v] += siz[u];
			if (siz[u] > siz[adj[v][0]]) swap(u, adj[v][0]);
		}
	}
	void dfsHld(int v) {
		pos[v] = tim++;
		for (int u : adj[v]) {
			rt[u] = (u == adj[v][0] ? rt[v] : u);
			dfsHld(u);
		}
	}
	template <class B> void process(int u, int v, B op) {
		for (; rt[u] != rt[v]; v = par[rt[v]]) {
			if (depth[rt[u]] > depth[rt[v]]) swap(u, v);
			op(pos[rt[v]], pos[v] + 1);
		}
		if (depth[u] > depth[v]) swap(u, v);
		op(pos[u] + VALS_EDGES, pos[v] + 1);
	}
	void modifyPath(int u, int v, int val = 1) {
		process(u, v, [&](int l, int r) { tree->set(l, r, val); });
	}
	int queryPath(int u, int v) { // Modify depending on problem
		int res = -1e9;
		process(u, v, [&](int l, int r) {
				res = max(res, tree->query(l, r));
		});
		return res;
	}
	int querySubtree(int v) { // modifySubtree is similar
		return tree->query(pos[v] + VALS_EDGES, pos[v] + siz[v]);
	}
};

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<vi> adj(n);
    F0R(i, n-1){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    HLD<0> H(adj);
    F0R(i, n){
        if(sz(adj[i])==1){
            H.modifyPath(0, i);
        }
    }
    while(q--){
        int m; cin >> m;
        set<int> l; 
        vi add;
        F0R(i, m){
            int t; cin >> t;
            t--; 
            if(sz(adj[t])!=1||l.count(t)) add.pb(t);
            l.insert(t);
        }
        trav(x, add) H.modifyPath(0, x);
        if(H.queryPath(0, 0)) cout << -1 << nl;
        else{
            cout << 2*(n-1)+m-H.querySubtree(0) << nl;
        }
        trav(x, add) H.modifyPath(0, x);
    }
    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