제출 #925601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925601		vjudge1	Joker (BOI20_joker)	C++17	0 / 100	2 ms	6488 KiB

Joker

#include<iostream>
#include<cassert>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<map>

using namespace std;

const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int MOD = (int)998244353;
const long long INF = (long long)1e18 + 7; 

int mult(int x, int y) {
	return 1ll*x*y%MOD;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	return x;
}

int sub(int x, int y) {
	x -= y;
	if(x < 0) {
		x += MOD;
	}
	return x;
}

int n, m, q;
pair<int, int> e[N];
vector<int> g[N];
int used[N];

bool dfs(int v) {
	for(auto to : g[v]) {
		if(!used[to]) {
			used[to] = 3-used[v];
			if(dfs(to)) {
				return 1;
			}
		} else if(used[to] == used[v]) {
			return 1;
		}
	}
	return 0;
}

bool solve(int l, int r) {
	for(int i = 1; i <= n; ++i) {
		g[i].clear();
		used[i] = 0;
	}
	for(int i = 1; i <= m; ++i) {
		if(i >= l && i <= r) {
			continue;
		}
		int u = e[i].first;
		int v = e[i].second;
		g[u].push_back(v);
		g[v].push_back(u);
	}             
	for(int i = 1; i <= n; ++i) {
		if(!used[i]) {
			used[i] = 1;
			if(dfs(i)) {
				return 1;
			}			
		}
	}
	return 0;
}

bool ans[N];

void init() {
	int l = 1, r = m, id = 0;
	while(l <= r) {
		int mid = (l+r)>>1;
   		if(solve(1, mid-1)) {
   			id = mid;
			l = mid+1;   			
   		} else {
   			r = mid-1;
   		}
	}
	for(int i = 1; i <= id; ++i) {
		ans[i] = 1;
	}
}

int main() {	
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= m; ++i) {
		cin >> e[i].first >> e[i].second;
	}       
	init();
	for(int i = 1; i <= q; ++i) {
		int l, r;
		cin >> l >> r;
		if(l == 1) {
			cout << (ans[r+1] ? "NO\n" : "YES\n");
			continue;
		}
		cout << (solve(l, r) ? "YES\n" : "NO\n");
	}
	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