Submission #1080005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080005		qwerasdfzxcl	Joker (BOI20_joker)	C++17	100 / 100	624 ms	22400 KiB

Joker

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
struct DSU{
	int path[400400], rank[400400];
	vector<array<int, 3>> st;
 
	void init(int n){
		st.clear();
		for (int i=1;i<=n;i++) path[i] = i, rank[i] = 0;
	}
	int find(int s){
		if (s==path[s]) return s;
		return find(path[s]);
	}
	void merge(int x, int y){
		x = find(x), y = find(y);
		if (x==y) {st.push_back({-1, -1, -1}); return;}
		if (rank[x] > rank[y]) swap(x, y);
		
		st.push_back({x, y, rank[y]});
		path[x] = y;
		if (rank[x]==rank[y]) rank[y]++;
	}
	void pop(int cnt){
		for (int i=1;i<=cnt;i++){
			auto [x, y, r] = st.back(); st.pop_back();
			if (x==-1) continue;
			path[x] = x;
			rank[y] = r;
		}
	}
}dsu;
 
int a[400400], b[400400], ans[400400], sz;
 
void rollback(int t){
	dsu.pop((sz-t) * 2);
	sz = t;
}
 
int push(int i){
	dsu.merge(a[i]*2, b[i]*2+1);
	dsu.merge(a[i]*2+1, b[i]*2);
	sz++;
	if (dsu.find(a[i]*2) == dsu.find(a[i]*2+1)) return 0;
	return 1;
}
 
void dnc(int l, int r, int s, int e){
	if (l > r) return;
	
	int m = (l+r)>>1;
	int t1 = sz;
 
	for (int i=min(r, s-1);i>=m;i--) push(i);
	int t2 = sz;
 
	for (int i=max(s, m);i<=e;i++){
		if (!push(i)) break;
		ans[m] = i;
	}
 
	rollback(t2);
	dnc(l, m-1, s, ans[m]);
 
	rollback(t1);
	for (int i=max(r+1, s);i<=ans[m]-1;i++) push(i);
	dnc(m+1, r, ans[m], e);
 
	rollback(t1);
 
}
 
int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	for (int i=1;i<=m;i++) scanf("%d %d", a+i, b+i);
	for (int i=1;i<=m;i++) a[i+m] = a[i], b[i+m] = b[i];
 
	dsu.init(n*2+3);
	dnc(1, m*2, 1, m*2);
	
	while(q--){
		int l, r;
		scanf("%d %d", &l, &r);
 
		int ll = r+1, rr = l-1 + m;
 
		if (ans[ll] >= rr) printf("NO\n");
		else printf("YES\n");
	}
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:80:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  for (int i=1;i<=m;i++) scanf("%d %d", a+i, b+i);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~
Joker.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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