제출 #1275169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275169		Bui_Quoc_Cuong	Joker (BOI20_joker)	C++20	0 / 100	0 ms	332 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;
pair <int, int> edges[N];
int L[N], R[N];

void init() {
	cin >> n >> m >> q;
	FOR(i, 1, m) {
		int u, v; cin >> u >> v;
		edges[i] = {u, v};
	}
	FOR(i, 1, q) {
		cin >> L[i] >> R[i];
	}
}

namespace subtask1 {
	struct DisjointSet {
		vector <int> lab;

		DisjointSet (int n) {
			lab.resize(2 * n + 2, - 1);
		}		

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

		bool joint (int u, int v) {
			int x = find(u), y = find(v);
			if (x == y) return false;
			if (lab[x] > lab[y]) swap(x, y);
			lab[x]+= lab[y];
			lab[y] = x;
			return true;
		}
	};

	void solve() {
		FOR(i, 1, q) {
			DisjointSet DSU(n);
			string res = "YES";
			FOR(j, L[i], R[i]) {
				int u = edges[j].first, v = edges[j].second;
				DSU.joint(u, v + n);
				DSU.joint(v, u + n);
				if (DSU.find(u) == DSU.find(u + n)) {
					res = "NO";
					break;
				}
				if (DSU.find(v) == DSU.find(v + n)) {
					res = "NO";
					break;
				}
			}	
			cout << res << "\n";
		}
	}
}

void process() {
	return subtask1::solve();
}		
	
signed main() {
	ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    init();
    process();

    return 0;
}

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