oj.uz

Submission #871044

# Submission time Handle Problem Language Result Execution time Memory
871044 2023-11-09T18:45:12 Z NaimSS Joker (BOI20_joker) C++14
100 / 100
 316 ms 42044 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
#define ld long double
#define ff first
#define ss second
#define endl '\n'
#define sz(v) ((int)v.size())
#define all(v) begin(v),end(v)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

void dbg_out() { cerr << endl ;}
template<typename Head, typename... Tail> void dbg_out(Head H,Tail... T){
	cerr<<' '<<H ;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr<<"("<< #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl;
#else 
#define dbg(...) 42
#endif

struct event{
	int a,b,psb,pa,corA,is_good;
	event(int a,int b,int psb,int pa,int corA,int is_good):
	a(a),b(b),psb(psb),pa(pa),corA(corA), is_good(is_good){}
};

struct DSU{
	vector<event> st;
	int is_good;
	int n;
	vi p,ps,ar;
	DSU(){}
	DSU(int n):n(n){
		p = ps = vi(n+1,1);
		ar = vi(n+1,0);
		rep(i,0,n+1)p[i] = i, ps[i] = 1, ar[i] = 0;
		is_good = 1;
	}
	int f(int x){
		while(x!=p[x])x = p[x];
		return x;
	}
	int cor(int x){
		int c=0;
		while(x!=p[x])c^=ar[x],x=p[x];
		return c;
	}
	pii F(int x){
		int c=0;
		while(x!=p[x])c^=ar[x],x=p[x];
		return pii(x,c);
	}
	bool join(int A,int B){
		auto [a,ca] = F(A);
		auto [b,cb] = F(B);
		if(ps[a] > ps[b])swap(a,b),swap(ca,cb);
		st.pb(event(a,b,ps[b],p[a],ar[a],is_good));
		if(a == b){
			if(ca == cb)is_good = 0;
			return 0;	
		}
		ps[b] += ps[a], p[a] = b;
		ar[a] = (ca^cb^1);
		// dbg(a,b,ps[a], ps[b], p[a], p[b]);
		return 1;
	}
	int can_add(int A,int B){
		auto [a,ca] = F(A);
		auto [b,cb] = F(B);
		if(a == b && ca == cb)return 0;
		return 1;
	}
	void undo(int qtd=1){
		while(qtd--){
			auto x = st.back();
			p[x.a] = x.pa,ps[x.b] = x.psb,is_good = x.is_good;
			ar[x.a] = x.corA;
			st.pop_back();
		}
	}
	void clear(){
		undo(sz(st));
	}
	int ok(){return is_good;}
	void push(pii x){
		join(x.ff,x.ss);
	}
	void pop(){ undo();}
};

const int N = 2 * (200100);
const int SQ = 400;
int a[N], b[N];
struct query{
	int l,r,id;
	query(int l,int r,int id):l(l),r(r),id(id){}
};
vector<query> Q[N];
int res[N];
#define F first
#define S second
DSU DS(N);
template<class U>
class ds_queue{
public:
	void push(U upd ){
		Q.push_back({upd, 1});
		DS.push(upd);
	}
	void pop(){
		if(!sz(Q))
			return;
		if(Q.back().S){
			vector< pair< U , bool> > block[2];
			do{
				block[Q.back().S].push_back(Q.back());
				Q.pop_back() , DS.pop();
			} while(sz(block[0]) != sz(block[1]) && sz(Q));
			if(!sz(block[0])){
				for(auto & w : block[1])
					w.S = 0 , DS.push(w.F);
				swap(Q,block[1]);
			}
			else{
				for(int j = 1; j >= 0 ; j --){
					while(sz(block[j])){
						auto w = block[j].back();
						block[j].pop_back();
						Q.push_back(w) , DS.push(w.F);
					}
				}
			}
		}
		DS.pop() , Q.pop_back();
	}
private:
	vector < pair< U , bool> > Q;
};
int first[N];

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m,qr;
	cin >> n >> m >> qr;
	for(int i=0;i<m;i++){
		cin >> a[i] >> b[i];
	}
	ds_queue<pii> q;
	vi first(2*m);
	int ptr=0;
	for(int i=0;i<2*m;i++){
		int A = a[i%m],B = b[i%m];
		while(!DS.can_add(A,B)){
			q.pop();
			ptr++;
		}
		q.push(pii(A,B));
		first[i] = ptr;
	}
	rep(i,0,qr){
		int l,r;
		cin >> l >> r;
		--l,--r;
		if(first[l  + m - 1] <= r + 1)cout << "NO\n";
		else cout<< "YES\n";
	}
	
}

Compilation message

Joker.cpp: In member function 'bool DSU::join(int, int)':
Joker.cpp:61:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   auto [a,ca] = F(A);
      |        ^
Joker.cpp:62:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |   auto [b,cb] = F(B);
      |        ^
Joker.cpp: In member function 'int DSU::can_add(int, int)':
Joker.cpp:75:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |   auto [a,ca] = F(A);
      |        ^
Joker.cpp:76:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |   auto [b,cb] = F(B);
      |        ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19292 KB Output is correct
6 Correct 5 ms 19540 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 5 ms 19548 KB Output is correct
10 Correct 5 ms 19548 KB Output is correct
11 Correct 5 ms 19516 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 7 ms 19800 KB Output is correct
14 Correct 5 ms 19548 KB Output is correct
15 Correct 5 ms 19548 KB Output is correct
16 Correct 5 ms 19548 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19392 KB Output is correct
19 Correct 6 ms 19548 KB Output is correct
20 Correct 6 ms 19372 KB Output is correct
21 Correct 5 ms 19548 KB Output is correct
22 Correct 6 ms 19548 KB Output is correct
23 Correct 5 ms 19548 KB Output is correct
24 Correct 6 ms 19548 KB Output is correct
25 Correct 5 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19548 KB Output is correct
28 Correct 6 ms 19548 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19292 KB Output is correct
6 Correct 5 ms 19540 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 5 ms 19548 KB Output is correct
10 Correct 5 ms 19548 KB Output is correct
11 Correct 5 ms 19516 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 7 ms 19800 KB Output is correct
14 Correct 5 ms 19548 KB Output is correct
15 Correct 5 ms 19548 KB Output is correct
16 Correct 5 ms 19548 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19392 KB Output is correct
19 Correct 6 ms 19548 KB Output is correct
20 Correct 6 ms 19372 KB Output is correct
21 Correct 5 ms 19548 KB Output is correct
22 Correct 6 ms 19548 KB Output is correct
23 Correct 5 ms 19548 KB Output is correct
24 Correct 6 ms 19548 KB Output is correct
25 Correct 5 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19548 KB Output is correct
28 Correct 6 ms 19548 KB Output is correct
29 Correct 6 ms 19548 KB Output is correct
30 Correct 6 ms 19548 KB Output is correct
31 Correct 7 ms 19512 KB Output is correct
32 Correct 6 ms 19548 KB Output is correct
33 Correct 7 ms 19544 KB Output is correct
34 Correct 6 ms 19548 KB Output is correct
35 Correct 6 ms 19548 KB Output is correct
36 Correct 7 ms 19508 KB Output is correct
37 Correct 6 ms 19560 KB Output is correct
38 Correct 6 ms 19644 KB Output is correct
39 Correct 6 ms 19548 KB Output is correct
40 Correct 7 ms 19548 KB Output is correct
41 Correct 7 ms 19556 KB Output is correct
42 Correct 6 ms 19544 KB Output is correct
43 Correct 6 ms 19544 KB Output is correct
44 Correct 6 ms 19548 KB Output is correct
45 Correct 7 ms 19552 KB Output is correct
46 Correct 8 ms 19548 KB Output is correct
47 Correct 7 ms 19548 KB Output is correct
48 Correct 7 ms 19548 KB Output is correct
49 Correct 7 ms 19544 KB Output is correct
50 Correct 6 ms 19544 KB Output is correct
51 Correct 6 ms 19548 KB Output is correct
52 Correct 7 ms 19548 KB Output is correct
53 Correct 6 ms 19548 KB Output is correct
54 Correct 7 ms 19548 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 310 ms 31132 KB Output is correct
4 Correct 74 ms 40480 KB Output is correct
5 Correct 136 ms 37248 KB Output is correct
6 Correct 150 ms 30364 KB Output is correct
7 Correct 167 ms 30364 KB Output is correct
8 Correct 147 ms 30108 KB Output is correct
9 Correct 179 ms 30496 KB Output is correct
10 Correct 192 ms 31360 KB Output is correct
11 Correct 212 ms 31816 KB Output is correct
12 Correct 171 ms 31624 KB Output is correct
13 Correct 124 ms 31148 KB Output is correct
14 Correct 157 ms 30780 KB Output is correct
15 Correct 203 ms 31136 KB Output is correct
16 Correct 207 ms 31428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19292 KB Output is correct
6 Correct 5 ms 19540 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 5 ms 19548 KB Output is correct
10 Correct 5 ms 19548 KB Output is correct
11 Correct 5 ms 19516 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 7 ms 19800 KB Output is correct
14 Correct 5 ms 19548 KB Output is correct
15 Correct 5 ms 19548 KB Output is correct
16 Correct 5 ms 19548 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19392 KB Output is correct
19 Correct 6 ms 19548 KB Output is correct
20 Correct 6 ms 19372 KB Output is correct
21 Correct 5 ms 19548 KB Output is correct
22 Correct 6 ms 19548 KB Output is correct
23 Correct 5 ms 19548 KB Output is correct
24 Correct 6 ms 19548 KB Output is correct
25 Correct 5 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19548 KB Output is correct
28 Correct 6 ms 19548 KB Output is correct
29 Correct 310 ms 31132 KB Output is correct
30 Correct 74 ms 40480 KB Output is correct
31 Correct 136 ms 37248 KB Output is correct
32 Correct 150 ms 30364 KB Output is correct
33 Correct 167 ms 30364 KB Output is correct
34 Correct 147 ms 30108 KB Output is correct
35 Correct 179 ms 30496 KB Output is correct
36 Correct 192 ms 31360 KB Output is correct
37 Correct 212 ms 31816 KB Output is correct
38 Correct 171 ms 31624 KB Output is correct
39 Correct 124 ms 31148 KB Output is correct
40 Correct 157 ms 30780 KB Output is correct
41 Correct 203 ms 31136 KB Output is correct
42 Correct 207 ms 31428 KB Output is correct
43 Correct 300 ms 31484 KB Output is correct
44 Correct 81 ms 41256 KB Output is correct
45 Correct 112 ms 37376 KB Output is correct
46 Correct 149 ms 30620 KB Output is correct
47 Correct 214 ms 30776 KB Output is correct
48 Correct 193 ms 30396 KB Output is correct
49 Correct 197 ms 31700 KB Output is correct
50 Correct 229 ms 31036 KB Output is correct
51 Correct 188 ms 31380 KB Output is correct
52 Correct 187 ms 31932 KB Output is correct
53 Correct 119 ms 30804 KB Output is correct
54 Correct 178 ms 30468 KB Output is correct
55 Correct 210 ms 31260 KB Output is correct
56 Correct 191 ms 31868 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19292 KB Output is correct
6 Correct 5 ms 19540 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 5 ms 19548 KB Output is correct
10 Correct 5 ms 19548 KB Output is correct
11 Correct 5 ms 19516 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 7 ms 19800 KB Output is correct
14 Correct 5 ms 19548 KB Output is correct
15 Correct 5 ms 19548 KB Output is correct
16 Correct 5 ms 19548 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19392 KB Output is correct
19 Correct 6 ms 19548 KB Output is correct
20 Correct 6 ms 19372 KB Output is correct
21 Correct 5 ms 19548 KB Output is correct
22 Correct 6 ms 19548 KB Output is correct
23 Correct 5 ms 19548 KB Output is correct
24 Correct 6 ms 19548 KB Output is correct
25 Correct 5 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19548 KB Output is correct
28 Correct 6 ms 19548 KB Output is correct
29 Correct 6 ms 19548 KB Output is correct
30 Correct 6 ms 19548 KB Output is correct
31 Correct 7 ms 19512 KB Output is correct
32 Correct 6 ms 19548 KB Output is correct
33 Correct 7 ms 19544 KB Output is correct
34 Correct 6 ms 19548 KB Output is correct
35 Correct 6 ms 19548 KB Output is correct
36 Correct 7 ms 19508 KB Output is correct
37 Correct 6 ms 19560 KB Output is correct
38 Correct 6 ms 19644 KB Output is correct
39 Correct 6 ms 19548 KB Output is correct
40 Correct 7 ms 19548 KB Output is correct
41 Correct 7 ms 19556 KB Output is correct
42 Correct 6 ms 19544 KB Output is correct
43 Correct 6 ms 19544 KB Output is correct
44 Correct 6 ms 19548 KB Output is correct
45 Correct 7 ms 19552 KB Output is correct
46 Correct 8 ms 19548 KB Output is correct
47 Correct 7 ms 19548 KB Output is correct
48 Correct 7 ms 19548 KB Output is correct
49 Correct 7 ms 19544 KB Output is correct
50 Correct 6 ms 19544 KB Output is correct
51 Correct 6 ms 19548 KB Output is correct
52 Correct 7 ms 19548 KB Output is correct
53 Correct 6 ms 19548 KB Output is correct
54 Correct 7 ms 19548 KB Output is correct
55 Correct 275 ms 31644 KB Output is correct
56 Correct 49 ms 39408 KB Output is correct
57 Correct 104 ms 36068 KB Output is correct
58 Correct 145 ms 29088 KB Output is correct
59 Correct 158 ms 29568 KB Output is correct
60 Correct 210 ms 31980 KB Output is correct
61 Correct 187 ms 31124 KB Output is correct
62 Correct 162 ms 31800 KB Output is correct
63 Correct 100 ms 29852 KB Output is correct
64 Correct 203 ms 30604 KB Output is correct
65 Correct 172 ms 31644 KB Output is correct

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19292 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 5 ms 19292 KB Output is correct
4 Correct 5 ms 19288 KB Output is correct
5 Correct 5 ms 19292 KB Output is correct
6 Correct 5 ms 19540 KB Output is correct
7 Correct 5 ms 19548 KB Output is correct
8 Correct 5 ms 19548 KB Output is correct
9 Correct 5 ms 19548 KB Output is correct
10 Correct 5 ms 19548 KB Output is correct
11 Correct 5 ms 19516 KB Output is correct
12 Correct 5 ms 19548 KB Output is correct
13 Correct 7 ms 19800 KB Output is correct
14 Correct 5 ms 19548 KB Output is correct
15 Correct 5 ms 19548 KB Output is correct
16 Correct 5 ms 19548 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 5 ms 19392 KB Output is correct
19 Correct 6 ms 19548 KB Output is correct
20 Correct 6 ms 19372 KB Output is correct
21 Correct 5 ms 19548 KB Output is correct
22 Correct 6 ms 19548 KB Output is correct
23 Correct 5 ms 19548 KB Output is correct
24 Correct 6 ms 19548 KB Output is correct
25 Correct 5 ms 19548 KB Output is correct
26 Correct 5 ms 19548 KB Output is correct
27 Correct 5 ms 19548 KB Output is correct
28 Correct 6 ms 19548 KB Output is correct
29 Correct 6 ms 19548 KB Output is correct
30 Correct 6 ms 19548 KB Output is correct
31 Correct 7 ms 19512 KB Output is correct
32 Correct 6 ms 19548 KB Output is correct
33 Correct 7 ms 19544 KB Output is correct
34 Correct 6 ms 19548 KB Output is correct
35 Correct 6 ms 19548 KB Output is correct
36 Correct 7 ms 19508 KB Output is correct
37 Correct 6 ms 19560 KB Output is correct
38 Correct 6 ms 19644 KB Output is correct
39 Correct 6 ms 19548 KB Output is correct
40 Correct 7 ms 19548 KB Output is correct
41 Correct 7 ms 19556 KB Output is correct
42 Correct 6 ms 19544 KB Output is correct
43 Correct 6 ms 19544 KB Output is correct
44 Correct 6 ms 19548 KB Output is correct
45 Correct 7 ms 19552 KB Output is correct
46 Correct 8 ms 19548 KB Output is correct
47 Correct 7 ms 19548 KB Output is correct
48 Correct 7 ms 19548 KB Output is correct
49 Correct 7 ms 19544 KB Output is correct
50 Correct 6 ms 19544 KB Output is correct
51 Correct 6 ms 19548 KB Output is correct
52 Correct 7 ms 19548 KB Output is correct
53 Correct 6 ms 19548 KB Output is correct
54 Correct 7 ms 19548 KB Output is correct
55 Correct 310 ms 31132 KB Output is correct
56 Correct 74 ms 40480 KB Output is correct
57 Correct 136 ms 37248 KB Output is correct
58 Correct 150 ms 30364 KB Output is correct
59 Correct 167 ms 30364 KB Output is correct
60 Correct 147 ms 30108 KB Output is correct
61 Correct 179 ms 30496 KB Output is correct
62 Correct 192 ms 31360 KB Output is correct
63 Correct 212 ms 31816 KB Output is correct
64 Correct 171 ms 31624 KB Output is correct
65 Correct 124 ms 31148 KB Output is correct
66 Correct 157 ms 30780 KB Output is correct
67 Correct 203 ms 31136 KB Output is correct
68 Correct 207 ms 31428 KB Output is correct
69 Correct 300 ms 31484 KB Output is correct
70 Correct 81 ms 41256 KB Output is correct
71 Correct 112 ms 37376 KB Output is correct
72 Correct 149 ms 30620 KB Output is correct
73 Correct 214 ms 30776 KB Output is correct
74 Correct 193 ms 30396 KB Output is correct
75 Correct 197 ms 31700 KB Output is correct
76 Correct 229 ms 31036 KB Output is correct
77 Correct 188 ms 31380 KB Output is correct
78 Correct 187 ms 31932 KB Output is correct
79 Correct 119 ms 30804 KB Output is correct
80 Correct 178 ms 30468 KB Output is correct
81 Correct 210 ms 31260 KB Output is correct
82 Correct 191 ms 31868 KB Output is correct
83 Correct 275 ms 31644 KB Output is correct
84 Correct 49 ms 39408 KB Output is correct
85 Correct 104 ms 36068 KB Output is correct
86 Correct 145 ms 29088 KB Output is correct
87 Correct 158 ms 29568 KB Output is correct
88 Correct 210 ms 31980 KB Output is correct
89 Correct 187 ms 31124 KB Output is correct
90 Correct 162 ms 31800 KB Output is correct
91 Correct 100 ms 29852 KB Output is correct
92 Correct 203 ms 30604 KB Output is correct
93 Correct 172 ms 31644 KB Output is correct
94 Correct 304 ms 33928 KB Output is correct
95 Correct 169 ms 42044 KB Output is correct
96 Correct 136 ms 39360 KB Output is correct
97 Correct 132 ms 33200 KB Output is correct
98 Correct 153 ms 33520 KB Output is correct
99 Correct 177 ms 33200 KB Output is correct
100 Correct 179 ms 34448 KB Output is correct
101 Correct 234 ms 32948 KB Output is correct
102 Correct 208 ms 34024 KB Output is correct
103 Correct 175 ms 33920 KB Output is correct
104 Correct 145 ms 33232 KB Output is correct
105 Correct 219 ms 33180 KB Output is correct
106 Correct 272 ms 34128 KB Output is correct
107 Correct 102 ms 40696 KB Output is correct
108 Correct 299 ms 33948 KB Output is correct
109 Correct 303 ms 33928 KB Output is correct
110 Correct 303 ms 33764 KB Output is correct
111 Correct 304 ms 34192 KB Output is correct
112 Correct 308 ms 33904 KB Output is correct
113 Correct 316 ms 33664 KB Output is correct
114 Correct 305 ms 34188 KB Output is correct
115 Correct 298 ms 33816 KB Output is correct
116 Correct 305 ms 33820 KB Output is correct