oj.uz

Submission #1054331

# Submission time Handle Problem Language Result Execution time Memory
1054331 2024-08-12T08:52:12 Z allin27x Joker (BOI20_joker) C++17
25 / 100
 196 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
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];

struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool conn(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	void unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
	}
};



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());
	DSU dsu1(2*n);
	DSU dsu2(2*n);
	DSU dsu3(2*n);
	int fM =0; 
	for (int t=0; t<SQRT; t++){
		for (int i=0; i<2*n; i++) dsu2.e[i] = dsu1.e[i];
		for (int i=0; i<2*n; i++) dsu3.e[i] = dsu1.e[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 (dsu3.conn(edges[ll][0],edges[ll][1])) f++;
					dsu3.unite(edges[ll][0]+n, edges[ll][1]);
					dsu3.unite(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 = a+n;
					dsu3.e[a] = dsu2.e[a];
					dsu3.e[b] = dsu2.e[b];
					dsu3.e[c] = dsu2.e[c];
					dsu3.e[d] = dsu2.e[d];

				}
				if (f || fm || fM) ans[p.i] = 1;
				j--;
				if (j<0) break;
				p = queries[t][j];
			}
			if (j<0) break;
			fm += dsu3.conn(edges[i][0], edges[i][1]);
			dsu2.unite(edges[i][0] + n, edges[i][1]);
			dsu2.unite(edges[i][0], edges[i][1] + n);
			dsu3.unite(edges[i][0] + n, edges[i][1]);
			dsu3.unite(edges[i][0], edges[i][1] + n);
			i--;
		}
		for (int ll=SQRT*t; ll<min(m, SQRT*t + SQRT); ll++){
			fM += dsu1.conn(edges[ll][0], edges[ll][1]);
			dsu1.unite(edges[ll][0] + n, edges[ll][1]);
			dsu1.unite(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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 121 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 121 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 125 ms 15992 KB Output is correct
4 Correct 180 ms 20404 KB Output is correct
5 Correct 175 ms 20144 KB Output is correct
6 Correct 121 ms 15288 KB Output is correct
7 Correct 137 ms 15128 KB Output is correct
8 Correct 93 ms 13240 KB Output is correct
9 Correct 128 ms 16076 KB Output is correct
10 Correct 196 ms 20148 KB Output is correct
11 Correct 121 ms 15544 KB Output is correct
12 Correct 176 ms 19892 KB Output is correct
13 Correct 68 ms 12484 KB Output is correct
14 Correct 96 ms 13496 KB Output is correct
15 Correct 152 ms 17492 KB Output is correct
16 Correct 194 ms 21000 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 121 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 121 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 121 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -