Submission #951289

#	Time	Username	Problem	Language	Result	Execution time	Memory
951289		koukirocks	Joker (BOI20_joker)	C++17	25 / 100	88 ms	23464 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 p[MAX];
int sz[MAX];
int rev[MAX];

void init() {
	for (int i=1;i<=n;i++) {
		p[i]=i;
		sz[i]=1;
		rev[i]=0;
	}
}

pii get(int a) {
	if (p[a]==a) return {a,0};
	else {
		auto [fa,c]=get(p[a]);
		return {fa,c^rev[a]};
	}
}

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);
	}
	init();
	int ans=0;
	for (int i=m;i>=1;i--) {
		edge eg=egs[i];
		auto [pa,ca]=get(eg.a);
		auto [pb,cb]=get(eg.b);
//		cout<<i<<" i\n";
//		cout<<eg.a<<" "<<pa<<" "<<ca<<"\n";
//		cout<<eg.b<<" "<<pb<<" "<<cb<<"\n";
		if (pa==pb) {
			if (ca==cb) {
				ans=i;
				break;
			}
		} else {
			if (sz[pa]<sz[pb]) {
				swap(pa,pb);
			}
			p[pb]=pa;
			sz[pa]+=sz[pb];
			rev[pb]=(ca==cb);
		}
	}
//	cout<<ans<<" ans\n";
	for (int i=1;i<=q;i++) {
		cin>>qry[i].l>>qry[i].r;
		qry[i].id=i;
		if (qry[i].r>=ans) cout<<"NO\n";
		else cout<<"YES\n";
	}
	return 0;
}

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