oj.uz

Submission #1054390

# Submission time Handle Problem Language Result Execution time Memory
1054390 2024-08-12T09:27:42 Z allin27x Joker (BOI20_joker) C++17
25 / 100
 101 ms 11200 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
#define forn(i,n) for(int i=0; i<n; i++)
#define readv(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
#define readvv(a,n,m) vector<vector<int>> a(n,vector<int>(m));forn(i,n)forn(j,m)cin>>a[i][j];
#define all(a) a.begin(), a.end()
#define _max(x,y) x = max(x,y)
#define _min(x,y) x = min(x,y)
// #define f first
// #define s second
 
const int N = 2e5+4;
const int SQRT = 460;
int ans[N];
 
struct qr{
	int l, r, i;
	bool operator<(qr b){
		return make_pair(l/SQRT, r) < make_pair(b.l/SQRT,b.r);
	}
};
 
vector<qr> queries[SQRT];
int edges[N][2];
 
int e1[2*N];
void build1(int N) {for (int i=0; i<N; i++) e1[i] = -1;}
int get1(int x) { return e1[x] < 0 ? x : e1[x] = get1(e1[x]); }
bool conn1(int a, int b) { return get1(a) == get1(b); }
int size1(int x) { return -e1[get1(x)]; }
void unite1(int x, int y) {
	x = get1(x), y = get1(y);
	if (x == y) return;
	if (e1[x] > e1[y]) swap(x, y);
	e1[x] += e1[y];
	e1[y] = x;
}
 
 
int e2[2*N];
void build2(int N) {for (int i=0; i<N; i++) e2[i] = -1;}
int get2(int x) { return e2[x] < 0 ? x : e2[x] = get2(e2[x]); }
bool conn2(int a, int b) { return get2(a) == get2(b); }
int size2(int x) { return -e2[get2(x)]; }
void unite2(int x, int y) {
	x = get2(x), y = get2(y);
	if (x == y) return;
	if (e2[x] > e2[y]) swap(x, y);
	e2[x] += e2[y];
	e2[y] = x;
}
 
int st[2*N];
 
 
void solve(){
	int n,m,q; cin>>n>>m>>q;
	for (int i=0; i<m; i++){
		int a,b; cin>>a>>b; a--;b--; edges[i][0]=a; edges[i][1] = b;
	}
	for (int i=0; i<q; i++){
		int l,r; cin>>l>>r; l--; r--;
		qr p; p.l=l;p.r=r;p.i=i;
		queries[l/SQRT].push_back(p);
	}
	for (int i=0; i<SQRT; i++) sort(queries[i].begin(), queries[i].end());
	build1(2*n); build2(2*n);
	int fM =0; 
	for (int t=0; t<SQRT; t++){
		for (int i=0; i<2*n; i++) e2[i] = e1[i],st[i]=e1[i];
		if (t*SQRT >= m) break;
		int fm = 0;
		int i = m-1; int j = queries[t].size()-1;
		while (i>=0){
			if (j<0) break;
			qr p = queries[t][j];
			while (p.r == i){
				int f = 0;
				for (int ll=t*SQRT; ll<p.l; ll++){
					if (conn2(edges[ll][0],edges[ll][1])) f++;
					unite2(edges[ll][0]+n, edges[ll][1]);
					unite2(edges[ll][0], edges[ll][1]+n);
				}
				for (int ll=t*SQRT; ll<p.l; ll++){
					int a = edges[ll][0]; int b = edges[ll][1];
					int c = a+n; int d = b+n;
					e2[a] = st[a];
					e2[b] = st[b];
					e2[c] = st[c];
					e2[d] = st[d];
 
 
				}
				if (f || fm || fM) ans[p.i] = 1;
				j--;
				if (j<0) break;
				p = queries[t][j];
			}
			if (j<0) break;
			fm += conn2(edges[i][0], edges[i][1]);
			unite2(edges[i][0] + n, edges[i][1]);
			unite2(edges[i][0], edges[i][1] + n);
			int a = edges[i][0]; int b = edges[i][1];
			int c = a+n; int d = b+n;
			st[a] = e2[a];
			st[b] = e2[b];
			st[c] = e2[c];
			st[d] = e2[d];
			i--;
		}
		for (int ll=SQRT*t; ll<min(m, SQRT*t + SQRT); ll++){
			fM += conn1(edges[ll][0], edges[ll][1]);
			unite1(edges[ll][0] + n, edges[ll][1]);
			unite1(edges[ll][0], edges[ll][1] + n);
		}
	}
	for (int i=0;i<q; i++) cout<<(ans[i]?"YES\n":"NO\n");
}
 
 
signed main(){ 
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t=1;
	while(t--){
		solve();
	}	
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 74 ms 11196 KB Output is correct
4 Correct 92 ms 9652 KB Output is correct
5 Correct 90 ms 10428 KB Output is correct
6 Correct 76 ms 10432 KB Output is correct
7 Correct 92 ms 10496 KB Output is correct
8 Correct 64 ms 10748 KB Output is correct
9 Correct 76 ms 10680 KB Output is correct
10 Correct 97 ms 11196 KB Output is correct
11 Correct 78 ms 10428 KB Output is correct
12 Correct 101 ms 11200 KB Output is correct
13 Correct 52 ms 10440 KB Output is correct
14 Correct 66 ms 10944 KB Output is correct
15 Correct 85 ms 10428 KB Output is correct
16 Correct 99 ms 10684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -