Submission #439549

#	Time	Username	Problem	Language	Result	Execution time	Memory
439549		soroush	Joker (BOI20_joker)	C++17	100 / 100	348 ms	13368 KiB

Joker

#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 = 4e5+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], par[maxn] , mn[maxn];
vector < pii > und;

int getpar(int v){
	while(par[v] > 0)v = par[v];
	return v;
}

void merge(int u, int v){
	if((u = getpar(u)) == (v = getpar(v)))return;
	if(par[v] < par[u])swap(u , v);
	und.pb({v, par[v]});
	par[u] += par[v] , par[v] = u;
}

void undo(){
	auto [v , w] = und.back() ; und.pop_back();
	par[par[v]] -= w , par[v] =  w;
}

void solve(int l , int r , int ur){
	if(l > r)return;
	int mid = (l + r) >> 1 , cp = und.size();
	for(int i = max(1 , l) ; i <= mid ; i ++){
		merge(a[i] , b[i] + n);
		merge(b[i] , a[i] + n);
		if(getpar(a[i]) == getpar(b[i])){
			for(int j = mid ; j <= r ; j ++)
				mn[j] = ur;
			while(und.size() > cp)undo();
			solve(l , mid - 1 , ur);
			return;
		}
	}
	int chp = und.size();
	for(int i = ur - 1 ; i > l ; i --){
		merge(a[i] , b[i] + n);
		merge(b[i] , a[i] + n);
		if(getpar(a[i]) == getpar(a[i] + n)){
			mn[mid] = i;
			break;
		}
	}
	while(und.size() > chp)undo();
	solve(mid + 1 , r , ur);
	while(und.size() > cp)undo();
	for(int i = ur - 1 ; i >= max(mn[mid] , l + 1) ; i --){
		merge(a[i] , b[i] + n);
		merge(b[i] , a[i] + n);
		if(getpar(a[i]) == getpar(b[i])){
			for(int j = l ; j < mid ; j ++)
				mn[j] = mn[mid];
			return;
		}
	}
	solve(l , mid - 1 , mn[mid]);
}

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 <= m ; i ++)
		cin >> a[i] >> b[i];
	solve(0 , m - 1 , m + 1);
	while(q --){
		int l , r;
		cin >> l >> r;
		cout << ((r < mn[l - 1]) ? "YES" : "NO") << endl;
	}
	return(0);
}

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int)':
Joker.cpp:50:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |    while(und.size() > cp)undo();
      |          ~~~~~~~~~~~^~~~
Joker.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |  while(und.size() > chp)undo();
      |        ~~~~~~~~~~~^~~~~
Joker.cpp:66:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |  while(und.size() > cp)undo();
      |        ~~~~~~~~~~~^~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29