Submission #877273

#	Time	Username	Problem	Language	Result	Execution time	Memory
877273		anhduc2701	Joker (BOI20_joker)	C++17	49 / 100	2053 ms	22476 KiB

Joker

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second 
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int n,m,q;
pair<int,int>ed[maxn];
vector<int>G[maxn];
int col[maxn];
int ok=0;
int par[maxn];
int lt[maxn];
int rt[maxn];
vector<int>que[maxn];
inline int fin(int u){
	if(par[u]==u)return u;
	int k=fin(par[u]);
	col[u]=col[par[u]]^col[u];
	return par[u]=k;
}
inline void join(int a,int b){
	int u=fin(a);
	int v=fin(b);
	if(u==v){
		if(col[a]==col[b]){
			ok=1;
		}
		return;
	}
	if(u>v){
		swap(u,v);
		swap(a,b);
	}
	col[v]=col[a]^col[b]^1;
	par[v]=u;
}
bool ans[maxn];
signed main(){
	// freopen("input.inp","r",stdin);
	// freopen("output.out","w",stdout);
	cin.tie(0),cout.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> q;
	for(int i=1;i<=m;i++){
		cin >> ed[i].fi >> ed[i].se;
	}
	if(q<=2000){
		for(int i=1;i<=q;i++){
			cin >> lt[i] >> rt[i];
			for(int j=1;j<=n;j++){
				col[j]=0;
				par[j]=j;
			}
			ok=0;
			for(int j=1;j<=lt[i]-1;j++){
				join(ed[j].fi,ed[j].se);
			}
			for(int j=rt[i]+1;j<=m;j++){
				join(ed[j].fi,ed[j].se);
			}
			if(ok==1){
				cout << "YES\n";
			}
			else{
				cout << "NO\n";
			}
		}
	}
	else{
		for(int i=1;i<=q;i++){
			cin >> lt[i] >> rt[i];
		}
		for(int i=1;i<=min(m,200);i++){
			for(int j=1;j<=m;j++)que[j].clear();
			for(int j=1;j<=q;j++){
				if(lt[j]==i ){
					que[rt[j]].pb(j);
				}
			}
			for(int j=1;j<=n;j++){
				par[j]=j;
				col[j]=0;
			}
			ok=0;
			for(int j=1;j<i;j++){
				join(ed[j].fi,ed[j].se);
			}
			for(int j=m;j>=i;j--){
				for(auto v:que[j]){
					ans[v]=ok;
				}
				join(ed[j].fi,ed[j].se);
			}
		}
		for(int i=1;i<=q;i++){
			if(ans[i])cout << "YES\n";
			else cout << "NO\n";
		}
	}
}

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