oj.uz

Submission #1054338

# Submission time Handle Problem Language Result Execution time Memory
1054338 2024-08-12T08:53:29 Z allin27x Joker (BOI20_joker) C++17
25 / 100
 203 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 = b+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 2396 KB Output is correct
2 Correct 0 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 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Runtime error 120 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 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 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Runtime error 120 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 127 ms 15284 KB Output is correct
4 Correct 179 ms 19932 KB Output is correct
5 Correct 176 ms 18772 KB Output is correct
6 Correct 119 ms 15032 KB Output is correct
7 Correct 120 ms 16188 KB Output is correct
8 Correct 93 ms 13240 KB Output is correct
9 Correct 130 ms 16000 KB Output is correct
10 Correct 192 ms 19972 KB Output is correct
11 Correct 120 ms 15148 KB Output is correct
12 Correct 174 ms 19636 KB Output is correct
13 Correct 69 ms 12984 KB Output is correct
14 Correct 95 ms 13236 KB Output is correct
15 Correct 187 ms 17332 KB Output is correct
16 Correct 203 ms 20912 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 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 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Runtime error 120 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 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 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Runtime error 120 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 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 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Runtime error 120 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -