Submission #1275210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275210		Bui_Quoc_Cuong	Joker (BOI20_joker)	C++20	0 / 100	254 ms	13124 KiB

Joker

#include         <bits/stdc++.h>

#define              ll   long long
#define              db   long double
#define             pLL   pair<ll, ll>
#define             pLI   pair<ll, int>
#define             pIL   pair<int, ll>
#define             pII   pair<int, int>
#define     FOR(i, a, b)  for (int i = a; i <= (int)b; i++)
#define     FORD(i, a, b) for (int i = a; i >= (int)b; i--)
#define         sz(a)     (int)a.size()         
#define          all(a)   a.begin(), a.end()
#define              eb   emplace_back
#define              pb   push_back
#define         MASK(a)   (1LL << (a))
#define     BIT(mask, i)  ((mask >> (i)) & 1LL)
#define         REP(i, n) for (int i = 0; i < n; i++)

using         namespace   std;

const ll          INF = 1e18;
const int        oo = 2e9;
const ll            MOD = 1e9 + 7;
const int         N = 5e5 + 5;

mt19937                   rd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll     Rand(ll L, ll R)   { return uniform_int_distribution<ll>(L, R)(rd); }

inline int     read() { 
    char c;    while (c = getchar(), c < '0' || c > '9'); int n = c - '0';
    while            (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
    return         n; }
template<   class T   >   bool maximize(T &a, T b) { if (b > a) return a = b, 1; return 0; }
template<   class T   >   bool minimize(T &a, T b) { if (b < a) return a = b, 1; return 0; }

ll      gcd(ll a, ll b)   { return b ? gcd(b, a % b) : a; }
ll      lcm(ll a, ll b)   { return a / gcd(a, b) * b; }

ll  fastPow(ll n, ll p, ll m = MOD)   { ll r = 1; for (n %= m; p; p >>= 1) { if (p & 1) (r *= n) %= m; (n *= n) %= m; } return r; }
ll         invMod(ll n, ll m = MOD)   { return fastPow(n, m - 2, m); }
#define        popcount   __builtin_popcountll
#define             clz   __builtin_clzll
#define             ctz   __builtin_ctzll

int n, m, q;
struct Edges {
	int u, v; 
	void input () {
		cin >> u >> v;
	}
} edges[N];
int ans[N];

struct DisjointSet {
	int lab[N];

	struct Data {
		int u, lu, v, lv, biparte;
	}; stack <Data> memo;

	bool biparte = true;

	int find (int x) {
		return lab[x] < 0 ? x : find(lab[x]);
	}

	void joint (int u, int v) {
		{	
			int x = find(u), y = find(v + n);
			if (x != y) {
				if (lab[x] > lab[y]) swap(x, y);
				memo.push({x, lab[x], y, lab[y], biparte});
				lab[x]+= lab[y];
				lab[y] = x;
				if (find(u) == find(u + n)) {
					biparte = false;
				}
				if (find(v) == find(v + n)) {
					biparte = false;
				}
			}
		}
		{
			int x = find(u + n), y = find(v);
			if (x != y) {
				if (lab[x] > lab[y]) swap(x, y);
				memo.push({x, lab[x], y, lab[y], biparte});
				lab[x]+= lab[y];
				lab[y] = x;
				if (find(v) == find(v + n)) {
					biparte = false;
				}
				if (find(u) == find(u + n)) {
					biparte = false;
				}
			}		
		}
	}

	int get_ver () {
		return (int) memo.size();
	}

	void roll_back (int ver) {
		while ((int)memo.size() > ver) {
			lab[memo.top().u] = memo.top().lu;
			lab[memo.top().v] = memo.top().lv;
			biparte = memo.top().biparte;
			memo.pop();
		}
	}
} DSU;

void init () {
	cin >> n >> m >> q;
	FOR(i, 1, m) edges[i].input();
}

void DnC (int L, int R, int opL, int opR) {
	if (L > R) return;
	int mid = (L + R) / 2;
	int opPos = opL;

	int old_vers = DSU.get_ver();	

	FOR(i, L, mid - 1) {
		DSU.joint(edges[i].u, edges[i].v);
	}

	if (DSU.biparte == false) {
		FOR(i, mid, R) ans[i] = m + 1;
		DSU.roll_back(old_vers);
		DnC(L, mid - 1, opL, opR);
		return;
	}

	FORD(i, opR, max(mid, opL)) {
		DSU.joint(edges[i].u, edges[i].v);
		if (DSU.biparte == false) {
			opPos = i;
			break;
		}
	}

	DSU.roll_back(old_vers);
	ans[mid] = opPos;

	old_vers = DSU.get_ver();
	FOR(i, L, mid) DSU.joint(edges[i].u, edges[i].v);
	DnC(mid + 1, R, opPos, R);
	DSU.roll_back(old_vers);

	old_vers = DSU.get_ver();
	FOR(i, mid + 1, R) DSU.joint(edges[i].u, edges[i].v);
	DnC(L, mid - 1, opL, opPos);
}	

void process () {
	FOR(i, 1, 2 * n) DSU.lab[i] = - 1;
	DnC(1, m, 1, m);
	while (q--) {
		int l, r; cin >> l >> r;
		cout << (ans[l] > r ? "YES" : "NO") << '\n';
	}
}

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

    #define kieuoanh "kieuoanh"
    if (fopen(kieuoanh".inp", "r")) {
        freopen(kieuoanh".inp", "r", stdin);
        freopen(kieuoanh".out", "w", stdout);
    }

    init();
    process();

    return 0;
}

Compilation message (stderr)

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

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