oj.uz

Submission #1055999

# Submission time Handle Problem Language Result Execution time Memory
1055999 2024-08-13T07:02:24 Z allin27x Joker (BOI20_joker) C++17
25 / 100
 406 ms 29684 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 && r!=0){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 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 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 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 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 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 206 ms 24660 KB Output is correct
4 Correct 406 ms 29216 KB Output is correct
5 Correct 98 ms 29140 KB Output is correct
6 Correct 95 ms 26320 KB Output is correct
7 Correct 143 ms 26236 KB Output is correct
8 Correct 126 ms 24640 KB Output is correct
9 Correct 130 ms 25812 KB Output is correct
10 Correct 179 ms 29144 KB Output is correct
11 Correct 144 ms 26184 KB Output is correct
12 Correct 134 ms 28968 KB Output is correct
13 Correct 99 ms 23604 KB Output is correct
14 Correct 121 ms 25040 KB Output is correct
15 Correct 161 ms 27524 KB Output is correct
16 Correct 170 ms 29684 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 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 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 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 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -