Submission #257891

#	Time	Username	Problem	Language	Result	Execution time	Memory
257891		arnold518	Joker (BOI20_joker)	C++14	100 / 100	710 ms	16544 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4e5;

int N, M, Q;
pii E[MAXN+10];
int ans[MAXN+10];

struct UF
{
	vector<int> par, sz, opp;
	bool state;
	vector<int> V;
	void init()
	{
		par.resize(2*N+10); sz.resize(2*N+10); opp.resize(2*N+10);
		int i, j;
		for(i=1; i<=N; i++) par[i]=i, sz[i]=1, opp[i]=N+i;
		for(i=1; i<=N; i++) par[i+N]=i+N, sz[i+N]=1, opp[i+N]=i;
		V.clear(); state=true;
	}
	int Find(int x)
	{
		if(x==par[x]) return x;
		return Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		int nx=opp[x], ny=opp[y];

		if(x==y || !state)
		{
			if(state) V.push_back(-1);
			else V.push_back(-2);
			state=false;
			return;
		}

		if(sz[x]<sz[ny]) swap(x, ny);
		if(sz[y]<sz[nx]) swap(y, nx);
		
		if(sz[x]==sz[ny]) sz[x]++, V.push_back(-3);
		if(sz[y]==sz[nx]) sz[y]++, V.push_back(-4);
		V.push_back(opp[x]); V.push_back(opp[y]); V.push_back(ny); V.push_back(nx);
		par[ny]=x;
		par[nx]=y;
		opp[x]=y; opp[y]=x;
	}
	void restore()
	{
		int ny, nx, x, y, oppx, oppy;
		if(V.empty()) while(1);
		if(V.back()==-1 || V.back()==-2)
		{
			if(V.back()==-1) state=true;
			V.pop_back();
		 	return;
		}

		nx=V.back(); V.pop_back();
		ny=V.back(); V.pop_back();
		oppy=V.back(); V.pop_back();
		oppx=V.back(); V.pop_back();
		x=par[ny]; y=par[nx];
		if(!V.empty() && V.back()==-4) sz[x]--, V.pop_back();
		if(!V.empty() && V.back()==-3) sz[y]--, V.pop_back();
		opp[x]=oppx; opp[y]=oppy;
		sz[x]-=sz[ny]; sz[y]-=sz[nx];
		par[ny]=ny; par[nx]=nx;
	}
}uf;

int P[MAXN+10];

void solve(int l1, int l2, int r1, int r2)
{
	int i, j;
	if(l1>l2) return;

	//printf("DNC %d %d %d %d\n", l1, l2, r1, r2);
	int lmid=l1+l2>>1;
	int cnt=0;
	for(i=max(1, l1); i<=lmid; i++) uf.Union(E[i].first, E[i].second), cnt++;
	for(i=r2; i>=r1 && i>lmid && uf.state; i--) uf.Union(E[i].first, E[i].second), cnt++;
	while(cnt--) uf.restore();
	int rmid=i; P[lmid]=rmid;
	for(i=r2; i>rmid; i--) uf.Union(E[i].first, E[i].second);
	solve(l1, lmid-1, r1, rmid);
	for(i=r2; i>rmid; i--) uf.restore();
	for(i=max(1, l1); i<=lmid; i++) uf.Union(E[i].first, E[i].second);
	solve(lmid+1, l2, rmid, r2);
	for(i=max(1, l1); i<=lmid; i++) uf.restore();
}

int main()
{
	int i, j, k;

	scanf("%d%d%d", &N, &M, &Q);
	for(i=1; i<=M; i++) scanf("%d%d", &E[i].first, &E[i].second);

	uf.init();
	solve(0, M, 1, M);
	//for(i=0; i<=M; i++) printf("%d ", P[i]);
	while(Q--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		if(r<=P[l-1]) printf("YES\n");
		else printf("NO\n");
	}
}

Compilation message (stderr)

Joker.cpp: In member function 'void UF::init()':
Joker.cpp:22:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:87:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int lmid=l1+l2>>1;
           ~~^~~
Joker.cpp:83:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
Joker.cpp: In function 'int main()':
Joker.cpp:103:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k;
         ^
Joker.cpp:103:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
Joker.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:106:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%d%d", &E[i].first, &E[i].second);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~

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