oj.uz

Submission #439518

# Submission time Handle Problem Language Result Execution time Memory
439518 2021-06-30T07:33:38 Z soroush Joker (BOI20_joker) C++17
0 / 100
 228 ms 9788 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5+10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n, m, q;
int a[maxn], b[maxn];
int par[maxn], sz[maxn];
bool val[maxn];
int mn[maxn];

int getpar(int v){
	return ((~par[v]) ? getpar(par[v]) : v);
}

bool getval(int v){
	return ((~par[v]) ? val[v] ^ getval(par[v]) : val[v]);
}

bool ok = 0;

vector < int > PAR;

void merge(int x){
	int u = a[x] , v = b[x];
	int pu = getpar(u) , pv = getpar(v);
	if(pu == pv){
		if(!ok and getval(u) == getval(v))
			PAR.pb(0);
		else
			PAR.pb(-1);
		ok |= getval(u) == getval(v);
		return;
	}
	if(sz[pu] > sz[pv])swap(pu , pv);
	PAR.pb(pu);
	val[pu] ^= getval(v) == getval(u);
	par[pu] = pv;
	sz[pv] += sz[pu];
}

void rollback(){
	int v = PAR.back();
	PAR.pop_back();
	if(v == -1)return;
	if(v == 0){
		ok = 0;
		return;
	}
	sz[par[v]] -= sz[v];
	par[v] = -1;
	
}

int L = 0 , R = 0;

void solve(int l , int r , int ul , int ur){
	if(l > r)return;
	if(ok) return;
	if(L ^ (l - 1))dokme("wf");
	assert(L == l - 1 and R == ur + 1);
	int mid = (l + r) / 2;
	while(L + 1 < mid){
		L++;
		merge(L);
	}if(ok)mn[mid] = m + 1;
	while(!ok){
		mn[mid] = R;
		R --;
		merge(R);
	}
	assert(ok);
	while(R < ur + 1)rollback(), R ++;
	while (L + 1 <= mid)L++, merge(L);
	assert(L == mid and R == ur + 1);
	solve(mid + 1 , r , mn[mid] , ur);
	assert(L == mid and R == ur + 1);
	while(L >= l){
		rollback() , L --;
	}
	while(R > mn[mid] + 1){
		merge(--R);
	}
	assert(L == l - 1 and R == min(m , mn[mid]) + 1);
	solve(l , mid - 1 , ul , min(m , mn[mid]));
	assert(L == l - 1 and R == min(m , mn[mid]) + 1);
	while(R < ur + 1){
		rollback(), R ++;
	}
	assert(L == l- 1 and R == ur + 1);
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> q;
	ms(par, -1);
	for(int i = 1 ; i <= n ; i ++)sz[i] = 1;
	for(int i = 1 ; i <= m ; i ++)
		cin >> a[i] >> b[i], merge(i);
	R = m + 1;
	cerr << endl;
	if(ok){
		for(int i = 1 ; i <= n ; i ++)sz[i] = 1;
		ms(par, -1) , ms(val , 0) , ok = 0;
		solve(1 , m , 1 , m);
	}
	while(q --){
		int l , r;
		cin >> l >> r;
		if(mn[l] == 0)mn[l] = m + 1;
		cout << ((r < mn[l] - 1) ? "YES" : "NO") << endl;
	}
	return(0);
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 228 ms 9788 KB Output is correct
4 Incorrect 116 ms 8872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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