Submission #905239

#	Time	Username	Problem	Language	Result	Execution time	Memory
905239		starchan	Joker (BOI20_joker)	C++17	100 / 100	369 ms	18280 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)2e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> pa(MX, -1);
vector<int> d(MX, 0);
bool works = true;
stack<in> roll;
in leader(int u)
{
	if(pa[u] < 0)
		return {u, 0};
	else
	{
		auto [v, x] = leader(pa[u]);
		return {v, x^d[u]};
	}
}

void undo()
{
	auto [v, w] = roll.top();
	roll.pop();
	if(w == 0)
	{
		works = v;
		return;
	}
	pa[v] = w;
	d[v] = 0;
	return;
}

void merge(int u, int v)
{

	auto [x, dx] = leader(u);
	auto [y, dy] = leader(v);

	if(x == y)
	{
		if(dx^dy^1)
		{
			roll.push({works, false});
			works =  false;
		}
		return;
	}

	if(pa[x] < pa[y])
		swap(x, y);//x has fewer elements now.
	roll.push({x, pa[x]});
	roll.push({y, pa[y]});
	pa[y]+=pa[x];
	pa[x] = y;
	d[x] = dx^dy^1;
	return;
}
//kk bipartite dsu (w rollback) ready.


vector<in> edges;
void add(int i)
{
	merge(edges[i].f, edges[i].s);
}

vector<int> opt;//opt[i] is smallest thing such that 1, 2, .., i-1, opt[i]+1, ..., n is bipartite. 
void dnc(int l, int r, int L, int R)//the DSU currently contains 1, 2, 3, .., l-1 and R+1, R+2, .., n
{
	if(l > r)
		return;
	int m = (l+r)/2;
	int SZ = roll.size();
	for(int i = l; i < m; i++)
		add(i);
	opt[m] = R;
	while(works && (opt[m] >= (m-1)))
	{
		add(opt[m]);
		opt[m]--;
	}
	opt[m]++;
	while(roll.size() > SZ)
		undo();
	for(int i = R; i > opt[m]; i--)
		add(i);
	dnc(l, m-1, L, opt[m]);
	while(roll.size() > SZ)
		undo();
	for(int i = l; i <= m; i++)
		add(i);
	dnc(m+1, r, opt[m], R);
	while(roll.size() > SZ)
		undo();
	return;
}
signed main()
{
	fast();
	int t = 1;
	while(t--)
	{
		int n, m, q;
		cin >> n >> m >> q;
		edges.resize(m+1);
		opt.resize(m+1);
		for(int i = 1; i <= m; i++)
			cin >> edges[i].f >> edges[i].s;
		int rr = INF;
		for(int i = 1; i <= m; i++)
		{
			add(i);
			if(works)
				continue;
			opt[i] = INF;
			rr = min(rr, i+1);
		}
		while(roll.size())
			undo();
		dnc(1, min(rr-1, m), 1, m);
		while(q--)
		{
			int l, r;
			cin >> l >> r;
			bool tt = (l < rr)&&(r>=opt[l]);
			cout << (tt? "NO\n" : "YES\n");
		}
	}
	return 0;
}	

Compilation message (stderr)

Joker.cpp: In function 'void dnc(long long int, long long int, long long int, long long int)':
Joker.cpp:91:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   91 |  while(roll.size() > SZ)
      |        ~~~~~~~~~~~~^~~~
Joker.cpp:96:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   96 |  while(roll.size() > SZ)
      |        ~~~~~~~~~~~~^~~~
Joker.cpp:101:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  101 |  while(roll.size() > SZ)
      |        ~~~~~~~~~~~~^~~~

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