Submission #1312923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312923		vlomaczk	Joker (BOI20_joker)	C++20	14 / 100	114 ms	12188 KiB

Joker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//Note - not my dsu just for testing whats wrong

struct DSU {
    vector<int> par;
    vector<int> rnk;
    vector<int> col;
    int odd;
    stack<array<int, 5>> history;

    DSU(int n) {
        par = vector<int>(n);
        iota(par.begin(), par.end(), 0);
        col = vector<int>(n, 0);
        rnk = vector<int>(n, 0);
        odd = 0;
    }

    pair<int, int> find(int x) {
        int c = col[x];
        while (par[x] != x) {
            x = par[x];
            c ^= col[x];
        }
        return {x, c};
    }

    void merge(int a, int b) {
        auto [pa, ca] = find(a);
        auto [pb, cb] = find(b);
        if (pa != pb) {
            if (rnk[pa] < rnk[pb]) swap(pa, pb);
            int dc = 0, dr = 0;
            if (ca == cb) dc = 1;
            if (rnk[pa] == rnk[pb]) dr = 1;
            par[pb] = pa;
            rnk[pa] += dr;
            col[pb] ^= dc;
            history.push({pa, pb, dr, dc, -1});
        } else if (ca == cb) {
            odd++;
            history.push({0, 0, 0, 0, 1});
        } else {
            history.push({0, 0, 0, 0, 0});
        }
    }

    void Rollback() {
        assert(!history.empty());
        auto t = history.top();
        history.pop();
        if (t[4] >= 0) {
            odd -= t[4];
            return;
        }
        col[t[1]] ^= t[3];
        rnk[t[0]] -= t[2];
        par[t[1]] = t[1];
    }
}dsu(200009);

vector<pair<int, int>> edges;
vector<int> last;

void cdq(int l1, int r1, int l2, int r2) { // We use divide & conquer cause i < j => last[i] <= last[j]
	if(l1>r1) return;
	int m = (l1+r1) / 2;
	int size1 = dsu.history.size();
	for(int i=l1; i<m; ++i) dsu.merge(edges[i].first, edges[i].second);
	last[m] = r2;
	int size2 = dsu.history.size();
	while(!dsu.odd && last[m] >= l2) {
		dsu.merge(edges[last[m]].first, edges[last[m]].second);
		last[m]--;
	}
	while(dsu.history.size() > size2) dsu.Rollback();
	dsu.merge(edges[m].first, edges[m].second);
	cdq(m+1, r1, last[m], r2);
	while(dsu.history.size() > size1) dsu.Rollback();
	for(int i=last[m]+1; i<=r2; ++i) dsu.merge(edges[i].first, edges[i].second);
	cdq(l1,m-1,l2,last[m]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n,m,q;
	cin >> n >> m >> q;
	edges.resize(m);
	last.resize(m);
	for(int i=0; i<m; ++i) {
		cin >> edges[i].first >> edges[i].second;
	}
	cdq(0,m-1,0,m-1);
	while(q--) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		if(r <= last[l]) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 22
• Subtask 5: 0 / 29
• Subtask 6: 6 / 6