Submission #470593

#	Time	Username	Problem	Language	Result	Execution time	Memory
470593		cp_is_hard	Joker (BOI20_joker)	C++14	100 / 100	1439 ms	20524 KiB

Joker

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b)

using namespace std;

#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else 
#define print(...)
#define vprint(...)
#endif
namespace dsu {
	int n, cnt, ops;
	vector<int> sz, par;
	vector<pii> ss, sp;
	void init_(int _n) {
		n = _n, cnt = 0, ops = 0;
		sz.assign(n + 1, 0);
		par.assign(n + 1, 0);
		rep(i, 1, n) 
			sz[i] = 1, par[i] = i;
	}
	int find_par(int a) {
		while(a != par[a]) a = par[a];
		return a;
	}
	bool same(int a, int b) {
		return find_par(a) == find_par(b);
	}
	void unite(int a, int b) {
		ops ++;
		int aa = find_par(a);
		int bb = find_par(b);
		if(aa == bb) return;
		if(sz[aa] < sz[bb]) swap(aa, bb);
		cnt++;
		sp.push_back({bb, par[bb]});
		ss.push_back({aa, sz[aa]});
		par[bb] = aa, sz[aa] += sz[bb];
	}
	void undo() {
		if(!cnt) return;
		cnt--;
		pii p;
		p = ss.back(), ss.pop_back();
		sz[p.first] = p.second;
		p = sp.back(), sp.pop_back();
		par[p.first] = p.second;
	}
};
namespace solver {
	int n, m;
	vector<int> s;
	vector<pii> es;
	void init_(int _n, int _m) {
		n = _n, m = _m;
		s.assign(2 * m, 0);
		es.assign(2 * m, {0, 0});
		dsu::init_(2 * n);
	}
	void solve(int L, int R, int l, int r) {
		int mid = (L + R) / 2, id = max(l, mid);
		if(L > R) return;
		int p1 = dsu::cnt;
		rep(i, mid, min(R, id - 1)) {
			dsu::unite(es[i].first, es[i].second + n);
			dsu::unite(es[i].first + n, es[i].second);
		} 
		int p2 = dsu::cnt;
		while(id < r) {
			int x = es[id].first, y = es[id].second;
			if(dsu::same(x, y)) break;
			dsu::unite(x, y + n);
			dsu::unite(x + n, y);
			id ++;
		}
		s[mid] = id;
		while(dsu::cnt != p2) dsu::undo();
		solve(L, mid - 1, l, id);
		while(dsu::cnt != p1) dsu::undo();
		rep(i, max(R + 1, l), id - 1) {
			dsu::unite(es[i].first, es[i].second + n);
			dsu::unite(es[i].first + n, es[i].second);
		} 
		solve(mid + 1, R, id, r);
		while(dsu::cnt != p1) dsu::undo();
		return;
	}
	bool query(int L, int R) {
		L --, R --;
		int l = R + 1, r = m + L - 1;
		return s[l] <= r; 
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	init_(n, m);
	rep(i, 0, m - 1) {
		cin >> es[i].first;
		cin >> es[i].second;
	}
	rep(i, m, 2 * m - 1) es[i] = es[i - m];
	solve(0, 2 * m - 1, 0, 2 * m);
	rep(i, 1, q) {
		int L, R;
		cin >> L >> R;
		cout << (query(L, R) ? "YES" : "NO") << "\n"; 
	}
	
	return 0;
}

Compilation message (stderr)

Joker.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
Joker.cpp:18:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
Joker.cpp:18:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

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