Submission #951198

#	Time	Username	Problem	Language	Result	Execution time	Memory
951198		koukirocks	Joker (BOI20_joker)	C++17	14 / 100	2045 ms	14684 KiB

Joker

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

int n,m,q;

struct edge {
	int a,b;
} egs[MAX];

vector<pii> G[MAX];

struct query{
	int l,r,id;
}qry[MAX];

int main() {
	speed;
	cin>>n>>m>>q;
	for (int i=1;i<=m;i++) {
		int a,b;
		cin>>a>>b;
		egs[i]={a,b};
		G[a].emplace_back(b,i);
		G[b].emplace_back(a,i);
	}
	for (int i=1;i<=q;i++) {
		cin>>qry[i].l>>qry[i].r;
		qry[i].id=i;
		bool flag=false;
		vector<int> clr(n+1,-1);
		queue<int> BFS;
		for (int st=1;st<=n;st++) {
			if (clr[st]!=-1) continue;
			clr[st]=0;
			BFS.push(st);
			while (!BFS.empty()) {
				int v=BFS.front();
				BFS.pop();
				for (auto [u,id]:G[v]) {
					if (qry[i].l<=id and id<=qry[i].r) continue;
					if (clr[u]==-1) {
						clr[u]=clr[v]^1;
						BFS.push(u);
					}
					if ((clr[u]^clr[v])==0) {
						flag=true;
						break;
					}
				}
				if (flag) break;
			}
			if (flag) break;
		}
		if (flag) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

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