제출 #858712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858712		maks007	Joker (BOI20_joker)	C++14	0 / 100	2024 ms	12052 KiB

Joker

#include "bits/stdc++.h"
 
using namespace std;
 
vector <vector <int> > g;
vector <int> used;
int f;
 
void dfs(int v, int dist = 1, int p = -1) {
	used[v] = 1;
	for(auto i : g[v]) {
		if(p == i) continue;
		if(!used[i]) dfs(i, dist+1, v);
		else {
			if((used[v] - used[i] + 1)%2==1) {
				// cout << v << " " << i << "\n";
				f = 1;
			}
		}
	}
}
 
signed main () {
	int n, m, q;
	cin >> n >> m >> q;
	g.resize(n);
	used.resize(n);
	vector <pair <int,int>> edge;
	for(int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		edge.push_back({u-1, v-1});
	}
	while(q --) {
		int l, r;
		cin >> l >> r;
		l --, r --;
		for(auto &i : g) i.clear();
		for(auto &i : used) i = 0;
		for(int i = 0; i < l; i ++) {
			g[edge[i].first].push_back(edge[i].second);
			g[edge[i].second].push_back(edge[i].first);
		}
		for(int i = r+1; i < m; i ++) {
			g[edge[i].first].push_back(edge[i].second);
			g[edge[i].second].push_back(edge[i].first);
		}
		for(int i = 0; i < n; i ++) {
			if(!used[i]) {
				f = 0;
				dfs(i);
				if(f) {
					cout << "YES\n";
					goto end;
				}
			}
		}
		cout << "NO\n";
		end:;
	}
	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