Submission #1299025

#TimeUsernameProblemLanguageResultExecution timeMemory
1299025floJoker (BOI20_joker)C++20
0 / 100
2094 ms10036 KiB
#include <bits/stdc++.h>
#define task "testing"
#define ll long long
#define multitest 0
using namespace std;

struct Edge {
	int u, v;
};

struct Queries {
	int l, r;
};

const int N = 2e5;

int n, m, q;

Edge E[N+5];

Queries Q[N+5];

bitset<N+5> res;

namespace sub12 {
	const int sN = 2e3;
	
	int dsu[2*sN+5];
	
	int flip(int v) {
		return v+(v <= n ? n : -n);
	}
	
	void reset() {
		fill(dsu+1, dsu+2*n+1, -1);
	}
	
	int root(int v) {
		return dsu[v] < 0 ? v : dsu[v] = root(dsu[v]);
	}
	
	void unite(int u, int v) {
		if ((u = root(u)) == (v = root(v))) return;
		
		if (dsu[u] > dsu[v]) swap(u, v);
		
		dsu[u] += dsu[v], dsu[v] = u;
	}
	
	bool connect(int u, int v) {
		return root(u) == root(v);
	}
	
	bool check() {
		return max({n, m, q}) <= sN;
	}
	
	bool qry(int l, int r) {
		reset();
		
		for (int x = 1; x < l; x++) {
			unite(E[x].u, flip(E[x].v));
			unite(flip(E[x].u), E[x].v);
		}
		
		for (int x = m; x > r; x--) {
			unite(E[x].u, flip(E[x].v));
			unite(flip(E[x].u), E[x].v);
		}
		
		for (int x = 1; x <= n; x++) {
			if (connect(x, flip(x))) return 1;
		}
		
		return 0;
	}
	
	void solve() {
		for (int x = 1; x <= q; x++) {
			if (qry(Q[x].l, Q[x].r)) res.set(x);
		}
	}
}

namespace sub34 {
	const int L = 200;
	
	int dsu[2*N+5], rt[L+5], mxL;
	
	bool check() {
		mxL = 0;
		
		for (int x = 1; x <= q; x++) {
			mxL = max(mxL, Q[x].l);
		}
		
		return mxL <= L;
	}
	
	int flip(int v) {
		return v+(v <= n ? n : -n);
	}
	
	void reset() {
		fill(dsu+1, dsu+2*n+1, -1);
	}
	
	int root(int v) {
		return dsu[v] < 0 ? v : dsu[v] = root(dsu[v]);
	}
	
	bool connect(int u, int v) {
		return root(u) == root(v);
	}
	
	bool unite(int u, int v) {
		if ((u = root(u)) == (v = root(v))) return 0;
		
		if (dsu[u] > dsu[v]) swap(u, v);
		
		dsu[u] += dsu[v], dsu[v] = u;
		
		return connect(u, flip(u)) || connect(v, flip(v));
	}
	
	void calc(int l) {
		reset();
		
		bool ex = 0;
		
		for (int x = 1; x < l && !ex; x++) {
			ex |= unite(E[x].u, flip(E[x].v));
			ex |= unite(flip(E[x].u), E[x].v);
		}
		
		if (ex) rt[l] = m+1;
		
		for (int r = m; r > l && !ex; r--) {
			ex |= unite(E[r].u, flip(E[r].v));
			ex |= unite(flip(E[r].u), E[r].v);
			
			if (ex) rt[l] = r;
		}
	}
	
	void solve() {
		for (int x = min(m, mxL); x >= 1; x--) calc(x);
		
		for (int x = 1; x <= q; x++) {
			if (Q[x].r < rt[Q[x].l]) res.set(x);
		}
	}
}

namespace sub56 {
	struct Data {
		bool cyc;
		
		int u, v, szu, szv, t;
	};
	
	bool cyc = 0;
	
	stack<Data> saved;
	
	int sz[2*N+5], par[2*N+5], rt[N+5], t = 0;
	
	int flip(int v) {
		return v+(v <= n ? n : -n);
	}
	
	int root(int v) {
		return par[v] == v ? v : root(par[v]);
	}
	
	bool connect(int u, int v) {
		return root(u) == root(v);
	}
	
	void unite(int u, int v) {
		if ((u = root(u)) == (v = root(v))) return;
		
		if (sz[u] < sz[v]) swap(u, v);
		
		saved.push({cyc, u, v, sz[u], sz[v], t});
		
		sz[u] += sz[v], par[v] = u, t++;
		
		cyc |= connect(u, flip(u));
		cyc |= connect(v, flip(v));
	}
	
	void roll(int T) {
		while (!saved.empty()) {
			Data cur = saved.top();
			
			if (cur.t == T) break;
			
			saved.pop();
			
			cyc = cur.cyc;
			
			sz[par[cur.u] = cur.u] = cur.szu;
			sz[par[cur.v] = cur.v] = cur.szv;
		}
		
		t = T;
	}
	
	void dnc(int l, int r, int opt) {
		if (l > r) return;
		
		int mid = (l+r)/2, cur = t;
		
		for (int x = l; x < mid; x++) {
			unite(E[x].u, flip(E[x].v));
			unite(flip(E[x].u), E[x].v);
		}
		
		rt[mid] = opt;
		
		while (rt[mid] >= mid && !cyc) {
			rt[mid]--;
			
			unite(E[rt[mid]].u, flip(E[rt[mid]].v));
			unite(flip(E[rt[mid]].u), E[rt[mid]].v);
		}
		
		roll(cur);
		
		for (int x = opt-1; x >= rt[mid]; x--) {
			unite(E[x].u, flip(E[x].v));
			unite(flip(E[x].u), E[x].v);
		}
		
		dnc(l, mid-1, rt[mid]);
		
		roll(cur);
		
		for (int x = mid; x <= rt[mid]; x++) {
			unite(E[x].u, flip(E[x].v));
			unite(flip(E[x].u), E[x].v);
		}
		
		dnc(mid+1, r, opt);
	}
	
	void solve() {
		for (int x = 2*n; x >= 1; x--) {
			sz[x] = 1, par[x] = x;
		}
		
		dnc(1, m, m+1);
		
		for (int x = 1; x <= q; x++) {
			if (Q[x].r < rt[Q[x].l]) res.set(x);
		}
	}
}

void flo(int ID) {
	cin >> n >> m >> q;
	
	for (int x = 1; x <= m; x++) {
		cin >> E[x].u >> E[x].v;
	}
	
	for (int x = 1; x <= q; x++) {
		cin >> Q[x].l >> Q[x].r;
	}
	
	sub56::solve();
	
	for (int x = 1; x <= q; x++) {
		cout << (res.test(x) ? "YES\n" : "NO\n");
	}
}

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

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

	int TCS = 1, ID = 1;

	if (multitest) {
		cin >> TCS;
	}

	while (TCS--) flo(ID++);

	return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:284:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  284 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:285:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  285 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...