Submission #1102068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102068		epicci23	Joker (BOI20_joker)	C++17	100 / 100	352 ms	101276 KiB

Joker

#include <iostream>
#include <fstream>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <functional>
#include <limits>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef vector<vector<int> > graph;

const double pi = acos(-1.0);

#define oned(a, x1, x2) { cout << #a << ":"; for(int _i = (x1); _i < (x2); _i++){ cout << " " << a[_i]; } cout << endl; }
#define twod(a, x1, x2, y1, y2) { cout << #a << ":" << endl; for(int _i = (x1); _i < (x2); _i++){ for(int _j = (y1); _j < (y2); _j++){ cout << (_j > y1 ? " " : "") << a[_i][_j]; } cout << endl; } }

#define mp make_pair
#define pb push_back
#define fst first
#define snd second

const int MAXN = 200005;

int parent[MAXN<<1];
int Size[MAXN<<1];

int depth = 0;
int par[50][MAXN<<1];
int sz[50][MAXN<<1];
vector<int> mem[50];

void setParent(int v, int p) {
	if(par[depth][v]==0) {
		par[depth][v] = parent[v];
		sz[depth][v] = Size[v];
		mem[depth].pb(v);
	}
	parent[v] = p;
}

int getParent(int v) {
	while(parent[v] != v) {
		v = parent[v];
	}
	return v;
}

bool mergeSets(int u, int v) {
	int pu = getParent(u<<1);
	int pv = getParent(v<<1);
	bool res;
	if((pu>>1) == (pv>>1)) {
		res = pu^pv;
	} else {
		if(Size[pu] > Size[pv]) {
			swap(pu,pv);
		}
		setParent(pu, pv^1);
		Size[pv^1] += Size[pu];
		setParent(pu^1, pv);
		Size[pv] += Size[pu^1];
		res = true;
	}
	return res;
}

void record() {
	depth++;
}

void rollback() {
	for(int i = 0; i < (int)mem[depth].size(); i++) {
		int v = mem[depth][i];
		Size[parent[v]] -= sz[depth][v];
		parent[v] = par[depth][v];
		Size[v] = sz[depth][v];
		par[depth][v] = 0;
	}
	mem[depth].clear();
	depth--;
}

int n, m, q, a[MAXN], b[MAXN], l[MAXN], r[MAXN];

void init() {
	for(int i = 2; i <= 2*n+1; i++) {
		parent[i] = i;
		Size[i] = 1;
	}
}

int last[MAXN];

void rec(int L1, int L2, int R1, int R2) {
	//cerr << L1 << ' ' << L2 << ' ' << R1 << ' ' << R2 << endl;
	
	record();
	
	int LM = (L1+L2)/2;
	for(int i = L1; i < LM; i++) {
		mergeSets(a[i],b[i]);
	}
	
	//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
	
	record();
	
	for(int i = R2; i >= LM; i--) {
		if(!mergeSets(a[i],b[i])) {
			last[LM] = i;
			break;
		}
	}
	
	rollback();
	
	//vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
	
	if(LM < L2) {
		mergeSets(a[LM],b[LM]);
		rec(LM+1,L2,max(LM+1,last[LM]),R2);
	}
	
	rollback();
	
	//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
	
	if(L1 < LM) {
		record();
		
		for(int i = R2; i > last[LM]; i--) {
			mergeSets(a[i],b[i]);
		}
		
		rec(L1,LM-1,R1,last[LM]);
		
		rollback();
	}
	
	//vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
}

void solve() {
	init();
	
	int X = 1;
	while(X <= m) {
		if(!mergeSets(a[X],b[X])) {
			break;
		}
		X++;
	}
	
	init();
	
	for(int i = X+1; i <= m; i++) {
		last[i] = m+1;
	}
	
	if(X <= m) {
		rec(1,X,1,m);
	}
	
	//oned(last,1,m+1);
	for(int i = 1; i <= m; i++) {
	//	printf("%d\n", last[i]);
	}
	
	for(int i = 1; i <= q; i++) {
		printf(last[l[i]] <= r[i] ? "NO\n" : "YES\n");
	}
}

int main() {
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	while(scanf("%d %d %d", &n, &m, &q)==3) {
		for(int i = 1; i <= m; i++) {
			scanf("%d %d", a+i, b+i);
		}
		for(int i = 1; i <= q; i++) {
			scanf("%d %d", l+i, r+i);
		}
		solve();
	}
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:196:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |    scanf("%d %d", a+i, b+i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
Joker.cpp:199:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |    scanf("%d %d", l+i, r+i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

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