Submission #716501

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
716501	2023-03-30T08:00:27 Z	josanneo22	Joker (BOI20_joker)	C++17	0 / 100	2000 ms	12640 KB

Joker

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>adj(2e5 + 6);
int n, V;
vector<int> colorArr(V);
void reset() {
	for (int i = 0; i < n; i++) {
		adj[i].clear();
	}
}
bool isBipartiteUtil(int src)
{
	colorArr[src] = 1;
	queue<int> q;
	q.push(src);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto& v : adj[u]) {
			if (u == v) return false;
			if (colorArr[v] == -1) {
				colorArr[v] = 1 - colorArr[u];
				q.push(v);
			}
			else if (colorArr[v] == colorArr[u]) return false;
		}
	}
	return true;
}
bool isBipartite()
{
	for (int i = 0; i < V; ++i) colorArr[i] = -1;
	for (int i = 0; i < V; i++)
		if (colorArr[i] == -1)
			if (isBipartiteUtil(i) == false)
				return false;
	return true;
}

int main()
{
	int m, q; cin >> n >> m >> q;
	V = n;
	vector<pair<int, int>> paths(m);
	for (auto& x : paths) {
		cin >> x.first >> x.second;
	}
	colorArr.resize(n+5);
	for (int i = 0; i < q; i++) {
		reset();
		int x, y; cin >> x >> y;
		x--; y--;
		for (int j = 0; j < m; j++) {
			if (x<=j && j<=y) continue;
			adj[paths[j].first].push_back(paths[j].second);
			adj[paths[j].second].push_back(paths[j].first);
		}
		if (!isBipartite()) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4900 KB	Output is correct
2	Correct	4 ms	5012 KB	Output is correct
3	Correct	4 ms	5012 KB	Output is correct
4	Correct	3 ms	4976 KB	Output is correct
5	Incorrect	4 ms	5004 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4900 KB	Output is correct
2	Correct	4 ms	5012 KB	Output is correct
3	Correct	4 ms	5012 KB	Output is correct
4	Correct	3 ms	4976 KB	Output is correct
5	Incorrect	4 ms	5004 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4900 KB	Output is correct
2	Correct	4 ms	5012 KB	Output is correct
3	Execution timed out	2039 ms	12640 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	4900 KB	Output is correct
2	Correct	4 ms	5012 KB	Output is correct
3	Correct	4 ms	5012 KB	Output is correct
4	Correct	3 ms	4976 KB	Output is correct
5	Incorrect	4 ms	5004 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #5

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4900 KB	Output is correct
2	Correct	4 ms	5012 KB	Output is correct
3	Correct	4 ms	5012 KB	Output is correct
4	Correct	3 ms	4976 KB	Output is correct
5	Incorrect	4 ms	5004 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #6

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4900 KB	Output is correct
2	Correct	4 ms	5012 KB	Output is correct
3	Correct	4 ms	5012 KB	Output is correct
4	Correct	3 ms	4976 KB	Output is correct
5	Incorrect	4 ms	5004 KB	Output isn't correct
6	Halted	0 ms	0 KB	-