Submission #1054367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1054367	2024-08-12T09:10:04 Z	allin27x	Joker (BOI20_joker)	C++17	25 / 100	131 ms	262144 KB

Joker

#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];
		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	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Runtime error	131 ms	262144 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Runtime error	131 ms	262144 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	63 ms	10552 KB	Output is correct
4	Correct	73 ms	9788 KB	Output is correct
5	Correct	74 ms	10440 KB	Output is correct
6	Correct	66 ms	10424 KB	Output is correct
7	Correct	63 ms	10552 KB	Output is correct
8	Correct	57 ms	10680 KB	Output is correct
9	Correct	64 ms	10684 KB	Output is correct
10	Correct	76 ms	10944 KB	Output is correct
11	Correct	70 ms	10432 KB	Output is correct
12	Correct	73 ms	10428 KB	Output is correct
13	Correct	53 ms	10448 KB	Output is correct
14	Correct	59 ms	10608 KB	Output is correct
15	Correct	71 ms	10940 KB	Output is correct
16	Correct	80 ms	10536 KB	Output is correct