Submission #722661

#	Time	Username	Problem	Language	Result	Execution time	Memory
722661		gagik_2007	Joker (BOI20_joker)	C++17	14 / 100	807 ms	176200 KiB

Joker

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

struct Query {
	int l;
	int r;
	int ind;
	ll ans;
	Query(int _l, int _r, int _ind) :l(_l), r(_r), ind(_ind), ans(0) {}
};

struct Edge {
	int x;
	int y;
	Edge(int _x, int _y) :x(_x), y(_y) {}
};

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 31;
ll n, m, k;
set<int>g[N];
deque<int>gd[N];
vector<Query>q;
vector<Edge>e;
int used[N];

// functions using set

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

bool is_odd_cycle() {
	for (int i = 1; i <= n; i++) {
		used[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		if (!used[i]) {
			used[i] = 1;
			if (dfs(i)) {
				return true;
			}
		}
	}
	return false;
}

void remove_edges(const Query& query) {
	for (int i = query.l; i <= query.r; i++) {
		g[e[i].x].erase(e[i].y);
		g[e[i].y].erase(e[i].x);
	}
}

void add_edges(const Query& query) {
	for (int i = query.l; i <= query.r; i++) {
		g[e[i].x].insert(e[i].y);
		g[e[i].y].insert(e[i].x);
	}
}

bool do_query(const Query& query) {
	remove_edges(query);
	bool res = is_odd_cycle();
	add_edges(query);
	return res;
}


// functions using deque

bool dfs_d(int v) {
	for (int to : gd[v]) {
		if (used[to] == used[v]) {
			return true;
		}
		else if (!used[to]) {
			used[to] = 3 - used[v];
			if (dfs_d(to)) {
				return true;
			}
		}
	}
	return false;
}

bool is_odd_cycle_d() {
	for (int i = 1; i <= n; i++) {
		used[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		if (!used[i]) {
			used[i] = 1;
			if (dfs_d(i)) {
				return true;
			}
		}
	}
	return false;
}

void remove_edges_d(const Query& query) {
	for (int i = query.l; i <= query.r; i++) {
		gd[e[i].x].pop_front();
		gd[e[i].y].pop_front();
	}
}

void add_edges_d(const Query& query) {
	for (int i = query.l; i <= query.r; i++) {
		gd[e[i].x].push_front(e[i].y);
		gd[e[i].y].push_front(e[i].x);
	}
}

bool do_query_d(const Query& query) {
	remove_edges_d(query);
	bool res = is_odd_cycle_d();
	add_edges_d(query);
	return res;
}

void only_l_equals_one() {
	// finding the first number i for which do_query(Query(0, i)) == false
	int l = 0, r = m + 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (do_query_d(Query(0, mid, 0))) {
			l = mid + 1;
		}
		else {
			r = mid;
		}
	}
	for (int i = 0; i < k; i++) {
		if (q[i].r >= l) {
			cout << "NO\n";
		}
		else cout << "YES\n";
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].insert(y);
		g[y].insert(x);
		gd[x].push_back(y);
		gd[y].push_back(x);
		e.push_back(Edge(x, y));
	}
	bool only1 = true;
	for (int i = 0; i < k; i++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		if (l != 0)only1 = false;
		q.push_back(Query(l, r, i));
	}
	if (n <= 2000 && m <= 2000 && k <= 2000) {
		for (int i = 0; i < k; i++) {
			if (do_query(q[i])) {
				cout << "YES\n";
			}
			else {
				cout << "NO\n";
			}
		}
	}
	else if (only1) {
		only_l_equals_one();
	}
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

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