제출 #930519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930519		Jawad_Akbar_JJ	Joker (BOI20_joker)	C++17	14 / 100	2086 ms	21492 KiB

Joker

#include <iostream>
#include <vector>

using namespace std;
const int N = (1<<18) + 1;
vector<pair<int,int>> nei[N];
int seen[N],h[N];
int cur = 1,l,r;
bool odd;


void dfs(int u,int k = 1){
	seen[u] = cur;
	h[u] = k;
	for (auto [i,j] : nei[u]){
		if (j <= r and j >= l)
			continue;
		if (seen[i] == cur){
			if ((h[u] - h[i]) % 2 == 0)
				odd = true;
		}
		else
			dfs(i,k+1);
	}
}


signed  main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m,q;
	cin>>n>>m>>q;

	for (int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		nei[a].push_back({b,i});
		nei[b].push_back({a,i});
	}

	while (q--){
		cin>>l>>r;
		odd = false;
		for (int i=1;i<=n;i++)
			if (seen[i]!=cur)
				dfs(i);
		cur++;
		if (odd)
			cout<<"YES"<<'\n';
		else
			cout<<"NO"<<'\n';
	}
}

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