oj.uz

Submission #299527

# Submission time Handle Problem Language Result Execution time Memory
299527 2020-09-15T06:16:46 Z E869120 Joker (BOI20_joker) C++14
0 / 100
 2000 ms 20344 KB 
#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];
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(1, 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");
	}
}

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]);
	
	solve_subtask1();
	return 0;
}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 4 ms 6528 KB Output is correct
7 Correct 5 ms 6528 KB Output is correct
8 Incorrect 6 ms 6528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 4 ms 6528 KB Output is correct
7 Correct 5 ms 6528 KB Output is correct
8 Incorrect 6 ms 6528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Execution timed out 2044 ms 20344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 4 ms 6528 KB Output is correct
7 Correct 5 ms 6528 KB Output is correct
8 Incorrect 6 ms 6528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 4 ms 6528 KB Output is correct
7 Correct 5 ms 6528 KB Output is correct
8 Incorrect 6 ms 6528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 4 ms 6528 KB Output is correct
7 Correct 5 ms 6528 KB Output is correct
8 Incorrect 6 ms 6528 KB Output isn't correct
9 Halted 0 ms 0 KB -