oj.uz

답안 #925907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925907 2024-02-12T10:34:47 Z vjudge1 Joker (BOI20_joker) C++17
14 / 100
 2000 ms 15320 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 4e5 + 1, mod = 998244353;

const ll inf = 1e9;
 
double eps = 1e-15;
                                                
bool flg = 0;

const int k = 210;

bool ok = 1, was[N];
vector<pii> g(N);

int p[N + 1], pr[N];
int sz[N + 1], pt[N + 1];
vector<array<int, 2>> h;

pii get(int x) {
 	if (p[x] == x) return {x, 0};
 	pii val = get(p[x]);
 	return {val.f, (pr[x] + val.s) % 2};
}

void add(int id) {
	int u = g[id].f;
	int v = g[id].s;
	pii x = get(u);
	pii y = get(v);
	if (x.f == y.f) {
		if (x.s == y.s) {
			if (ok) {
			    h.push_back({-1, -1});
				ok = 0;
			}    
		}
		return;
	}
	if (sz[x.f] > sz[y.f]) swap(x, y);
	h.push_back({x.f, sz[x.f]});
	h.push_back({y.f, sz[y.f]});
	p[x.f] = y.f;
	pr[x.f] = (x.s + y.s + 1) % 2;  	
	sz[y.f] += sz[x.f];
}

void rb() {
	while (sz(h) && !pt[sz(h)]) {
		array<int, 2> x = h.back();
		h.pop_back();
		if (x[0] == -1) {
			ok = 1;
			continue;
		}
		p[x[0]] = x[0];
		pr[x[0]] = 0;
		sz[x[0]] = x[1];
	}
	pt[sz(h)] = 0; 
}

bool slave(int l, int r) {
	for (int i = l; i <= r; i++) add(i);
	bool vv = ok;
	rb();
	return vv;	
}

bool cmp(array<int, 3> a, array<int, 3> b) {
	if (a[0] / k < b[0] / k) return 1;
	if (a[0] / k == b[0] / k && a[1] < b[1]) return 1;
	return 0;
}

void slv() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[i] = g[i + m] = {u, v};
	}
	for (int i = 1; i <= n; i++) 
		p[i] = i, sz[i] = 1;
	vector<array<int, 3>> qr;
	bool ans[q + 1];
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		int tl = r + 1, tr = l + m - 1;
		if (tl / k == tr / k) 
			ans[i] = slave(tl, tr);
		else qr.push_back({tl, tr, i});
	}
	sort(all(qr), cmp);
	int tr = 0, lst = -1, pos;
	for (auto [l, r, id]: qr) {
		if (l / k != lst) {
			rb();
			lst = l / k;
			pos = (lst + 1) * k - 1;
			tr = pos;
		}
		while (tr < r) 
			add(++tr);
		pt[sz(h)] = 1;
		for (int i = pos; i >= l; i--) 
			add(i);
		ans[id] = ok;
		rb();
		
	}
	for (int i = 1; i <= q; i++) {
		if (ans[i]) cout << "NO\n";
		else cout << "YES\n";
	}
}                                                                           
 
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {  	
		slv();
	}
}
//wenomechainsama

Compilation message

Joker.cpp:140:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  140 | main() {
      | ^~~~
Joker.cpp: In function 'void slv()':
Joker.cpp:128:3: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |   for (int i = pos; i >= l; i--)
      |   ^~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 2 ms 9560 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct
12 Correct 2 ms 9564 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 3 ms 9588 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 2 ms 9564 KB Output is correct
18 Correct 3 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9564 KB Output is correct
22 Correct 2 ms 9564 KB Output is correct
23 Correct 2 ms 9560 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 2 ms 9564 KB Output is correct
26 Correct 2 ms 9564 KB Output is correct
27 Correct 2 ms 9560 KB Output is correct
28 Correct 2 ms 9560 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 2 ms 9560 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct
12 Correct 2 ms 9564 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 3 ms 9588 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 2 ms 9564 KB Output is correct
18 Correct 3 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9564 KB Output is correct
22 Correct 2 ms 9564 KB Output is correct
23 Correct 2 ms 9560 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 2 ms 9564 KB Output is correct
26 Correct 2 ms 9564 KB Output is correct
27 Correct 2 ms 9560 KB Output is correct
28 Correct 2 ms 9560 KB Output is correct
29 Correct 7 ms 9820 KB Output is correct
30 Correct 6 ms 9820 KB Output is correct
31 Correct 7 ms 9816 KB Output is correct
32 Correct 7 ms 9820 KB Output is correct
33 Correct 6 ms 9820 KB Output is correct
34 Correct 6 ms 9820 KB Output is correct
35 Correct 8 ms 9820 KB Output is correct
36 Correct 5 ms 9820 KB Output is correct
37 Correct 7 ms 9820 KB Output is correct
38 Correct 9 ms 9820 KB Output is correct
39 Correct 7 ms 9816 KB Output is correct
40 Correct 6 ms 9820 KB Output is correct
41 Correct 7 ms 9844 KB Output is correct
42 Correct 6 ms 9820 KB Output is correct
43 Correct 5 ms 9820 KB Output is correct
44 Correct 5 ms 9820 KB Output is correct
45 Correct 6 ms 9820 KB Output is correct
46 Correct 6 ms 9816 KB Output is correct
47 Correct 5 ms 9820 KB Output is correct
48 Correct 8 ms 9820 KB Output is correct
49 Correct 7 ms 9820 KB Output is correct
50 Correct 7 ms 9824 KB Output is correct
51 Correct 6 ms 9820 KB Output is correct
52 Correct 6 ms 9820 KB Output is correct
53 Correct 7 ms 9820 KB Output is correct
54 Correct 7 ms 9820 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Execution timed out 2060 ms 14540 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 2 ms 9560 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct
12 Correct 2 ms 9564 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 3 ms 9588 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 2 ms 9564 KB Output is correct
18 Correct 3 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9564 KB Output is correct
22 Correct 2 ms 9564 KB Output is correct
23 Correct 2 ms 9560 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 2 ms 9564 KB Output is correct
26 Correct 2 ms 9564 KB Output is correct
27 Correct 2 ms 9560 KB Output is correct
28 Correct 2 ms 9560 KB Output is correct
29 Execution timed out 2060 ms 14540 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 2 ms 9560 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct
12 Correct 2 ms 9564 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 3 ms 9588 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 2 ms 9564 KB Output is correct
18 Correct 3 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9564 KB Output is correct
22 Correct 2 ms 9564 KB Output is correct
23 Correct 2 ms 9560 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 2 ms 9564 KB Output is correct
26 Correct 2 ms 9564 KB Output is correct
27 Correct 2 ms 9560 KB Output is correct
28 Correct 2 ms 9560 KB Output is correct
29 Correct 7 ms 9820 KB Output is correct
30 Correct 6 ms 9820 KB Output is correct
31 Correct 7 ms 9816 KB Output is correct
32 Correct 7 ms 9820 KB Output is correct
33 Correct 6 ms 9820 KB Output is correct
34 Correct 6 ms 9820 KB Output is correct
35 Correct 8 ms 9820 KB Output is correct
36 Correct 5 ms 9820 KB Output is correct
37 Correct 7 ms 9820 KB Output is correct
38 Correct 9 ms 9820 KB Output is correct
39 Correct 7 ms 9816 KB Output is correct
40 Correct 6 ms 9820 KB Output is correct
41 Correct 7 ms 9844 KB Output is correct
42 Correct 6 ms 9820 KB Output is correct
43 Correct 5 ms 9820 KB Output is correct
44 Correct 5 ms 9820 KB Output is correct
45 Correct 6 ms 9820 KB Output is correct
46 Correct 6 ms 9816 KB Output is correct
47 Correct 5 ms 9820 KB Output is correct
48 Correct 8 ms 9820 KB Output is correct
49 Correct 7 ms 9820 KB Output is correct
50 Correct 7 ms 9824 KB Output is correct
51 Correct 6 ms 9820 KB Output is correct
52 Correct 6 ms 9820 KB Output is correct
53 Correct 7 ms 9820 KB Output is correct
54 Correct 7 ms 9820 KB Output is correct
55 Correct 1559 ms 12004 KB Output is correct
56 Execution timed out 2037 ms 15320 KB Time limit exceeded
57 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 2 ms 9560 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 2 ms 9560 KB Output is correct
12 Correct 2 ms 9564 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 3 ms 9588 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 2 ms 9564 KB Output is correct
18 Correct 3 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9564 KB Output is correct
22 Correct 2 ms 9564 KB Output is correct
23 Correct 2 ms 9560 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 2 ms 9564 KB Output is correct
26 Correct 2 ms 9564 KB Output is correct
27 Correct 2 ms 9560 KB Output is correct
28 Correct 2 ms 9560 KB Output is correct
29 Correct 7 ms 9820 KB Output is correct
30 Correct 6 ms 9820 KB Output is correct
31 Correct 7 ms 9816 KB Output is correct
32 Correct 7 ms 9820 KB Output is correct
33 Correct 6 ms 9820 KB Output is correct
34 Correct 6 ms 9820 KB Output is correct
35 Correct 8 ms 9820 KB Output is correct
36 Correct 5 ms 9820 KB Output is correct
37 Correct 7 ms 9820 KB Output is correct
38 Correct 9 ms 9820 KB Output is correct
39 Correct 7 ms 9816 KB Output is correct
40 Correct 6 ms 9820 KB Output is correct
41 Correct 7 ms 9844 KB Output is correct
42 Correct 6 ms 9820 KB Output is correct
43 Correct 5 ms 9820 KB Output is correct
44 Correct 5 ms 9820 KB Output is correct
45 Correct 6 ms 9820 KB Output is correct
46 Correct 6 ms 9816 KB Output is correct
47 Correct 5 ms 9820 KB Output is correct
48 Correct 8 ms 9820 KB Output is correct
49 Correct 7 ms 9820 KB Output is correct
50 Correct 7 ms 9824 KB Output is correct
51 Correct 6 ms 9820 KB Output is correct
52 Correct 6 ms 9820 KB Output is correct
53 Correct 7 ms 9820 KB Output is correct
54 Correct 7 ms 9820 KB Output is correct
55 Execution timed out 2060 ms 14540 KB Time limit exceeded
56 Halted 0 ms 0 KB -