Submission #1293903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293903		shidou26	Joker (BOI20_joker)	C++20	100 / 100	256 ms	21708 KiB

Joker

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

#ifdef KURUMI
    #include "algo/debug.h"
#endif

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]" 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
    if(seed == 0) return rand(l, r);
    else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;

const int N = 2e5 + 3;

int n, m, q;
int l[N], r[N];
struct Edge {int u, v;} edge[N];

void input() {
	cin >> n >> m >> q;

	for(int i = 1; i <= m; i++) {
		cin >> edge[i].u >> edge[i].v;
	}

	for(int i = 1; i <= q; i++) {
		cin >> l[i] >> r[i];
	}
}

struct UnionFind {
	int bipartite;
	vector<int> lab, save;
	vector<pair<int&, int>> history;

	UnionFind (int n) : bipartite(1), lab(2 * n + 3) {
		for(int i = 1; i <= 2 * n; i++) {
			lab[i] = -1;
		}
	}

	int root(int u) {
		return lab[u] < 0 ? u : root(lab[u]);
	}

	bool unite(int u, int v) {
		u = root(u); v = root(v);
		if(u == v) return false;
		if(lab[u] > lab[v]) swap(u, v);
		history.emplace_back(lab[u], lab[u]);
		history.emplace_back(lab[v], lab[v]);
		lab[u] += lab[v];
		lab[v] = u;
		return true;
	}

	void clause(int u, int v) {
		// cout << "Adding " << dbg(u) << dbg(v) << endl;

		// u and v with different sides
		unite(u, v + n);
		unite(v, u + n);

		// bipartite false 
		if(root(u) == root(u + n) || root(v) == root(v + n)) {
			history.emplace_back(bipartite, bipartite);
			bipartite = 0;
		} 
	}

	void persist() {save.push_back(sz(history));}
	void rollback() {
		// cout << "Removing " << endl;
		int t = save.back(); save.pop_back();
		while(t < sz(history)) {
			// cout << history.back().fi << " " << history.back().se << endl;
			history.back().fi = history.back().se;
			history.pop_back();
		}
	}
};

namespace subtask_2 {
	bool approve() {
		return max({n, m, q}) <= 2000;
	}

	void execute() {
		UnionFind dsu(n);
		for(int i = 1; i <= q; i++) {
			// cout << dsu.bipartite << " " << sz(dsu.history) << " " << sz(dsu.save) << endl;
			dsu.persist();
			// for(int j = 1; j <= n; j++) cout << dsu.root(j) << " \n"[j == n];
			for(int j = 1; j < l[i]; j++) dsu.clause(edge[j].u, edge[j].v);
			for(int j = r[i] + 1; j <= m; j++) dsu.clause(edge[j].u, edge[j].v);
			cout << (!dsu.bipartite ? "YES" : "NO") << endl;
			dsu.rollback();
		}
	}
}

namespace subtask_5 {
	bool approve() {
		return q <= 1000;
	}

	namespace Block {
		const int S = 2000;

		int block(int id) {
			return (id - 1) / S + 1;
		}

		int low(int id) {
			return (id - 1) * S + 1;
		}

		int up(int id) {
			return min(m, id * S);
		}
	} 
	using namespace Block;

	bool answer[N];
	vector<int> query[N];

	void execute() {
		UnionFind dsu(n);

		for(int i = 1; i <= q; i++) {
			if((l[i] - 1) + (m - r[i]) <= S) {
				dsu.persist();
				for(int j = 1; j < l[i]; j++) dsu.clause(edge[j].u, edge[j].v);
				for(int j = r[i] + 1; j <= m; j++) dsu.clause(edge[j].u, edge[j].v);
				answer[i] = !dsu.bipartite;
				dsu.rollback();
				continue;
			}

			query[block(l[i])].emplace_back(i);
		}

		int num_block = block(m);

		for(int b = 1, lpt = 1; b <= num_block; b++) {
			if(query[b].empty()) continue;
			sort(all(query[b]), [&](int x, int y) {
				return r[x] > r[y];
			});	

			// cout << dbg(b) << endl;
			// cout << dbg(query[b]) << endl;

			int lft = low(b);
			int pointer = m;

			while(lpt < lft) {
				dsu.clause(edge[lpt].u, edge[lpt].v);
				lpt++;
			}

			dsu.persist();
			for(int i : query[b]) {
				while(r[i] < pointer) {
					dsu.clause(edge[pointer].u, edge[pointer].v);
					pointer--;
				}

				dsu.persist();
				for(int j = lft; j < l[i]; j++) dsu.clause(edge[j].u, edge[j].v);
				answer[i] = !dsu.bipartite;
				dsu.rollback();
			}
			dsu.rollback();
		}

		for(int i = 1; i <= q; i++) {
			cout << (answer[i] ? "YES" : "NO") << endl;
		}
	}
}

namespace subtask_6 {
	bool approve() {
		return true;
	}

	int last[N];

	void solve(int l, int r, int opt_l, int opt_r, UnionFind &dsu) {
		if(l > r) return;	
		int mid = (l + r) >> 1;

		dsu.persist();
		for(int i = l; i < mid; i++) {
			dsu.clause(edge[i].u, edge[i].v);
		}

		dsu.persist();
		last[mid] = mid;
		if(!dsu.bipartite) last[mid] = opt_r;
		else {
			for(int i = opt_r - 1; i >= mid; i--) {
				dsu.clause(edge[i].u, edge[i].v);
				if(!dsu.bipartite) {
					last[mid] = i;
					break;
				}
			}
		} 

		dsu.rollback();
		dsu.clause(edge[mid].u, edge[mid].v);
		solve(mid + 1, r, last[mid], opt_r, dsu);

		dsu.rollback();
		for(int i = opt_r - 1; i >= last[mid]; i--) dsu.clause(edge[i].u, edge[i].v);
		solve(l, mid - 1, opt_l, last[mid], dsu);
	}

	void execute() {
		UnionFind dsu(n);
		solve(1, m, 1, m + 1, dsu);

		// for(int i = 1; i <= n; i++) cout << last[i] << " \n"[i == n];
		for(int i = 1; i <= q; i++) {
			cout << (r[i] < last[l[i]] ? "YES" : "NO") << endl;
		}
	}
}

void process() {
    if(subtask_2::approve()) return subtask_2::execute();
    if(subtask_5::approve()) return subtask_5::execute();
    if(subtask_6::approve()) return subtask_6::execute();
}

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

    #define task "Deeto"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    int testcase = 1; // cin >> testcase;    
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
    cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
    
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:276:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  276 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:277:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  277 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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