Submission #722646

#	Time	Username	Problem	Language	Result	Execution time	Memory
722646		gagik_2007	Joker (BOI20_joker)	C++17	14 / 100	506 ms	37748 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 ind;
	int l;
	int r;
	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];
vector<Query>q;
vector<Edge>e;
int used[N];

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;
}

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);
		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";
			}
		}
	}
}

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

Compilation message (stderr)

Joker.cpp: In constructor 'Query::Query(int, int, int)':
Joker.cpp:32:6: warning: 'Query::r' will be initialized after [-Wreorder]
   32 |  int r;
      |      ^
Joker.cpp:30:6: warning:   'int Query::ind' [-Wreorder]
   30 |  int ind;
      |      ^~~
Joker.cpp:34:2: warning:   when initialized here [-Wreorder]
   34 |  Query(int _l, int _r, int _ind) :l(_l), r(_r), ind(_ind), ans(0) {}
      |  ^~~~~
Joker.cpp: In function 'int main()':
Joker.cpp:118:7: warning: variable 'only1' set but not used [-Wunused-but-set-variable]
  118 |  bool only1 = true;
      |       ^~~~~

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