Submission #716501

#	Time	Username	Problem	Language	Result	Execution time	Memory
716501		josanneo22	Joker (BOI20_joker)	C++17	0 / 100	2039 ms	12640 KiB

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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29