Submission #1017835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017835		VMaksimoski008	Joker (BOI20_joker)	C++17	100 / 100	207 ms	25796 KiB

Joker

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

array<int, 2> E[200008];
int last[200008];
 
struct Disjoint_Set_Union {
	static const int N = 2e5;
	int par[N + 8], dis[N + 8], sz[N + 8];
	vector<pair<int*, int>> history; int is_bi = 1;
	Disjoint_Set_Union() {
		iota(par, par + N + 8, 0);
		fill(dis, dis + N + 8, 0);
		fill(sz, sz + N + 8, 1);
	}
	pair<int, int> pu, pv; int du, dv;
	pair<int, int> find(int u) {
		du = 0;
		while (par[u] != u) du ^= dis[u], u = par[u];
		return {u, du};
	}
	void uni(int u, int v) {
		pu = find(u); pv = find(v);
		u = pu.first; du = pu.second; v = pv.first; dv = pv.second;
		if (u == v) {
			if (du == dv) history.push_back({&is_bi, is_bi}), is_bi = 0;
			return;
		}
		if (sz[u] < sz[v]) swap(u, v);
		history.push_back({par + v, par[v]});
		history.push_back({dis + v, dis[v]});
		history.push_back({sz + u, sz[u]});
		par[v] = u; dis[v] = du ^ dv ^ 1; sz[u] += sz[v];
	}
	int snap() {return history.size();}
	void roll(int snapshot) {
		while (history.size() > snapshot) {
			*history.back().first = history.back().second;
			history.pop_back();
		}
	}
} dsu;

void f(int l, int r, int tl, int tr) {
    if(l > r) return ;
    int mid = (l + r) / 2, ss = dsu.snap();

    for(int i=l; i<mid; i++) dsu.uni(E[i][0], E[i][1]);
    int ss2 = dsu.snap();

    for(int i=tr; i>=max(mid, tl); i--) {
        if(!dsu.is_bi) {
            last[mid] = i;
            break;
        }

        dsu.uni(E[i][0], E[i][1]);
    }

    if(!last[mid]) last[mid] = mid - 1;

    dsu.roll(ss2);
    dsu.uni(E[mid][0], E[mid][1]);
    f(mid+1, r, last[mid], tr);
    dsu.roll(ss);
    for(int i=tr; i>last[mid]; i--) dsu.uni(E[i][0], E[i][1]);
    f(l, mid-1, tl, last[mid]);
    dsu.roll(ss);
}

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

    int n, m, q;
    cin >> n >> m >> q;

    for(int i=1; i<=m; i++) cin >> E[i][0] >> E[i][1];

    f(1, m, 1, m);
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << (last[l] < r ? "NO" : "YES") << '\n';
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp: In member function 'void Disjoint_Set_Union::roll(int)':
Joker.cpp:50:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |   while (history.size() > snapshot) {
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~

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