Submission #299529

#	Time	Username	Problem	Language	Result	Execution time	Memory
299529		E869120	Joker (BOI20_joker)	C++14	39 / 100	2041 ms	22520 KiB

Joker

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

// Input
int N;
int M, A[1 << 18], B[1 << 18];
int Q, L[1 << 18], R[1 << 18];

// Graph
vector<int> X[1 << 18];
int col[1 << 18];
int lim[1 << 18];
bool flag;

void dfs(int pos, int dep) {
	col[pos] = dep;
	for (int i : X[pos]) {
		if (col[i] != -1) {
			if (col[i] == dep) flag = true;
			continue;
		}
		dfs(i, dep ^ 1);
	}
}

bool solve(int l, int r) {
	flag = false;
	for (int i = 1; i <= N; i++) X[i].clear();
	for (int i = 1; i <= M; i++) {
		if (l <= i && i <= r) continue;
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= N; i++) col[i] = -1;
	for (int i = 1; i <= N; i++) {
		if (col[i] >= 0) continue;
		dfs(i, 0);
	}
	return flag;
}

void solve_subtask1() {
	for (int i = 1; i <= Q; i++) {
		bool ans = solve(L[i], R[i]);
		if (ans == false) printf("NO\n");
		else printf("YES\n");
	}
}

void solve_subtask3() {
	int maxL = 0;
	for (int i = 1; i <= Q; i++) maxL = max(maxL, L[i]);
	for (int i = 1; i <= maxL; i++) {
		int cl = i, cr = M + 1, cm;
		for (int j = 0; j < 20; j++) {
			cm = (cl + cr) / 2;
			bool I = solve(i, cm);
			if (I == true) { lim[i] = max(lim[i], cm); cl = cm; }
			else { cr = cm; }
		}
	}
	
	for (int i = 1; i <= Q; i++) {
		if (R[i] <= lim[L[i]]) printf("YES\n");
		else printf("NO\n");
	}
}

int main() {
	scanf("%d%d%d", &N, &M, &Q);
	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]);
	
	if (N <= 2000 && M <= 2000 && Q <= 2000) solve_subtask1();
	else solve_subtask3();
	return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:71:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  for (int i = 1; i <= M; i++) scanf("%d%d", &A[i], &B[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:72:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |  for (int i = 1; i <= Q; i++) scanf("%d%d", &L[i], &R[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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