oj.uz

Submission #1056001

# Submission time Handle Problem Language Result Execution time Memory
1056001 2024-08-13T07:03:34 Z allin27x Joker (BOI20_joker) C++17
25 / 100
 373 ms 25608 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ll __int128
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

struct DSU{
	vector<int> par;
	vector<int> size;
	stack<int> rb;
	stack<char> tp;
	stack<int> bad;
	stack<pair<int,int>> edg;
	int nb;  int A = 0; int k;
	DSU(int n){
		k = n/2; par.resize(n); for(int i=0; i<n; ++i) par[i]=i;
		size.resize(n,1); nb = 0;
	}
	int get(int p){
		return par[p]==p? p: get(par[p]);
	}
	void unite(int a, int b){
		edg.push({a,b});
		if (get(a%k) == get(b%k)) {
			nb++; bad.push(1);
		} else bad.push(0);
		a = get(a); b = get(b);
		if (a==b){
			rb.push(-1);
			return;
		}
		if (size[a] > size[b]) swap(a,b);
		rb.push(a);
		size[b]+=size[a];
		par[a] = b;
	}
	void rollbackHelper(){
		int f = rb.top();
		rb.pop();
		nb -= bad.top(); bad.pop();
		edg.pop();
		if (f==-1) return;
		size[par[f]] -= size[f];
		par[f] = f;
	}
	void change(){
		stack<pair<int,int>> edA,edB;
		edB.push({edg.top().first, edg.top().second}); rollbackHelper();
		int a=0, b=1; tp.pop();
		while (A!=a && a!=b){
			if (tp.top()=='A'){
				a++; edA.push({edg.top().first, edg.top().second}); 
			} else {
				b++; edB.push({edg.top().first, edg.top().second}); 
			}
			tp.pop(); rollbackHelper();
		}
		while (!edB.empty()){
			unite(edB.top().first, edB.top().second);
			edB.pop();
			tp.push('B');
		}
		while (!edA.empty()){
			unite(edA.top().first, edA.top().second);
			edA.pop();
			tp.push('A'); 
		}
	}

	void rollback(){
		if (tp.top() == 'B') change();
		int f = rb.top();
		rb.pop();
		nb -= bad.top(); bad.pop();
		A--; tp.pop(); edg.pop();
		if (f==-1) return;
		size[par[f]] -= size[f];
		par[f] = f;
	}
};


const int N = 2e5+4;
int ans[N];
int edg[N][2];

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--; 
		edg[i][0] = a; edg[i][1] = b;
	}
	DSU dsu(2*n);
	for (int i=0; i<=m-1; i++){
		dsu.tp.push('A'); dsu.tp.push('A'); dsu.A+=2;
		dsu.unite(edg[i][0], edg[i][1]+n);
		dsu.unite(edg[i][0]+n, edg[i][1]);
	}
	int l=m-1; 
	for (int r = m-1; r>=0; r--){
		while (l>=0 && dsu.nb){
			l--;
			dsu.rollback(); dsu.rollback();
		}
		ans[r]  = l+1;
		if (l==r){dsu.rollback(); dsu.rollback(); l--;}
		dsu.unite(edg[r][0], edg[r][1] + n);
		dsu.unite(edg[r][0] + n, edg[r][1]);
		dsu.tp.push('B'); dsu.tp.push('B');
	}
	while (q--){
		int l, r; cin>>l>>r; l--; r--;
		cout<<(ans[r]<=l? "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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 223 ms 22224 KB Output is correct
4 Correct 373 ms 25540 KB Output is correct
5 Correct 110 ms 24792 KB Output is correct
6 Correct 94 ms 22228 KB Output is correct
7 Correct 106 ms 22224 KB Output is correct
8 Correct 119 ms 21196 KB Output is correct
9 Correct 132 ms 22484 KB Output is correct
10 Correct 207 ms 25608 KB Output is correct
11 Correct 154 ms 22308 KB Output is correct
12 Correct 131 ms 24788 KB Output is correct
13 Correct 100 ms 19948 KB Output is correct
14 Correct 160 ms 21024 KB Output is correct
15 Correct 156 ms 23504 KB Output is correct
16 Correct 185 ms 25556 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -