oj.uz

답안 #989371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989371 2024-05-28T05:27:12 Z qwerasdfzxcl Joker (BOI20_joker) C++17
0 / 100
 1 ms 4440 KB 
#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[200200], b[200200], ans[200200], 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);

	dsu.init(n*2+3);
	dnc(1, m, 1, m);
	
	while(q--){
		int l, r;
		scanf("%d %d", &l, &r);
		if (ans[l] >= r) printf("YES\n");
		else printf("NO\n");
	}
}

Compilation message

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:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -