oj.uz

Submission #722661

# Submission time Handle Problem Language Result Execution time Memory
722661 2023-04-12T14:20:54 Z gagik_2007 Joker (BOI20_joker) C++17
14 / 100
 807 ms 176200 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 144332 KB Output is correct
2 Correct 85 ms 144324 KB Output is correct
3 Correct 84 ms 144244 KB Output is correct
4 Correct 83 ms 144308 KB Output is correct
5 Correct 84 ms 144332 KB Output is correct
6 Correct 86 ms 144340 KB Output is correct
7 Correct 86 ms 144332 KB Output is correct
8 Correct 87 ms 144332 KB Output is correct
9 Correct 86 ms 144296 KB Output is correct
10 Correct 88 ms 144372 KB Output is correct
11 Correct 89 ms 144312 KB Output is correct
12 Correct 86 ms 144316 KB Output is correct
13 Correct 86 ms 144280 KB Output is correct
14 Correct 82 ms 144384 KB Output is correct
15 Correct 84 ms 144336 KB Output is correct
16 Correct 86 ms 144300 KB Output is correct
17 Correct 90 ms 144376 KB Output is correct
18 Correct 103 ms 144372 KB Output is correct
19 Correct 96 ms 144448 KB Output is correct
20 Correct 103 ms 144360 KB Output is correct
21 Correct 96 ms 144332 KB Output is correct
22 Correct 95 ms 144284 KB Output is correct
23 Correct 102 ms 144416 KB Output is correct
24 Correct 104 ms 144388 KB Output is correct
25 Correct 88 ms 144356 KB Output is correct
26 Correct 98 ms 144376 KB Output is correct
27 Correct 90 ms 144296 KB Output is correct
28 Correct 87 ms 144312 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 144332 KB Output is correct
2 Correct 85 ms 144324 KB Output is correct
3 Correct 84 ms 144244 KB Output is correct
4 Correct 83 ms 144308 KB Output is correct
5 Correct 84 ms 144332 KB Output is correct
6 Correct 86 ms 144340 KB Output is correct
7 Correct 86 ms 144332 KB Output is correct
8 Correct 87 ms 144332 KB Output is correct
9 Correct 86 ms 144296 KB Output is correct
10 Correct 88 ms 144372 KB Output is correct
11 Correct 89 ms 144312 KB Output is correct
12 Correct 86 ms 144316 KB Output is correct
13 Correct 86 ms 144280 KB Output is correct
14 Correct 82 ms 144384 KB Output is correct
15 Correct 84 ms 144336 KB Output is correct
16 Correct 86 ms 144300 KB Output is correct
17 Correct 90 ms 144376 KB Output is correct
18 Correct 103 ms 144372 KB Output is correct
19 Correct 96 ms 144448 KB Output is correct
20 Correct 103 ms 144360 KB Output is correct
21 Correct 96 ms 144332 KB Output is correct
22 Correct 95 ms 144284 KB Output is correct
23 Correct 102 ms 144416 KB Output is correct
24 Correct 104 ms 144388 KB Output is correct
25 Correct 88 ms 144356 KB Output is correct
26 Correct 98 ms 144376 KB Output is correct
27 Correct 90 ms 144296 KB Output is correct
28 Correct 87 ms 144312 KB Output is correct
29 Correct 178 ms 144480 KB Output is correct
30 Correct 381 ms 144644 KB Output is correct
31 Correct 440 ms 144788 KB Output is correct
32 Correct 547 ms 144656 KB Output is correct
33 Correct 584 ms 144652 KB Output is correct
34 Correct 442 ms 144736 KB Output is correct
35 Correct 405 ms 144668 KB Output is correct
36 Correct 458 ms 144688 KB Output is correct
37 Correct 346 ms 144808 KB Output is correct
38 Correct 262 ms 144644 KB Output is correct
39 Correct 495 ms 144672 KB Output is correct
40 Correct 535 ms 144672 KB Output is correct
41 Correct 490 ms 144592 KB Output is correct
42 Correct 467 ms 144776 KB Output is correct
43 Correct 169 ms 144588 KB Output is correct
44 Correct 162 ms 144644 KB Output is correct
45 Correct 165 ms 144740 KB Output is correct
46 Correct 156 ms 144656 KB Output is correct
47 Correct 503 ms 144716 KB Output is correct
48 Correct 480 ms 144716 KB Output is correct
49 Correct 463 ms 144624 KB Output is correct
50 Correct 422 ms 144676 KB Output is correct
51 Correct 536 ms 144844 KB Output is correct
52 Correct 500 ms 144664 KB Output is correct
53 Correct 464 ms 144660 KB Output is correct
54 Correct 411 ms 144784 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 144332 KB Output is correct
2 Correct 85 ms 144324 KB Output is correct
3 Incorrect 807 ms 176200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 144332 KB Output is correct
2 Correct 85 ms 144324 KB Output is correct
3 Correct 84 ms 144244 KB Output is correct
4 Correct 83 ms 144308 KB Output is correct
5 Correct 84 ms 144332 KB Output is correct
6 Correct 86 ms 144340 KB Output is correct
7 Correct 86 ms 144332 KB Output is correct
8 Correct 87 ms 144332 KB Output is correct
9 Correct 86 ms 144296 KB Output is correct
10 Correct 88 ms 144372 KB Output is correct
11 Correct 89 ms 144312 KB Output is correct
12 Correct 86 ms 144316 KB Output is correct
13 Correct 86 ms 144280 KB Output is correct
14 Correct 82 ms 144384 KB Output is correct
15 Correct 84 ms 144336 KB Output is correct
16 Correct 86 ms 144300 KB Output is correct
17 Correct 90 ms 144376 KB Output is correct
18 Correct 103 ms 144372 KB Output is correct
19 Correct 96 ms 144448 KB Output is correct
20 Correct 103 ms 144360 KB Output is correct
21 Correct 96 ms 144332 KB Output is correct
22 Correct 95 ms 144284 KB Output is correct
23 Correct 102 ms 144416 KB Output is correct
24 Correct 104 ms 144388 KB Output is correct
25 Correct 88 ms 144356 KB Output is correct
26 Correct 98 ms 144376 KB Output is correct
27 Correct 90 ms 144296 KB Output is correct
28 Correct 87 ms 144312 KB Output is correct
29 Incorrect 807 ms 176200 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 144332 KB Output is correct
2 Correct 85 ms 144324 KB Output is correct
3 Correct 84 ms 144244 KB Output is correct
4 Correct 83 ms 144308 KB Output is correct
5 Correct 84 ms 144332 KB Output is correct
6 Correct 86 ms 144340 KB Output is correct
7 Correct 86 ms 144332 KB Output is correct
8 Correct 87 ms 144332 KB Output is correct
9 Correct 86 ms 144296 KB Output is correct
10 Correct 88 ms 144372 KB Output is correct
11 Correct 89 ms 144312 KB Output is correct
12 Correct 86 ms 144316 KB Output is correct
13 Correct 86 ms 144280 KB Output is correct
14 Correct 82 ms 144384 KB Output is correct
15 Correct 84 ms 144336 KB Output is correct
16 Correct 86 ms 144300 KB Output is correct
17 Correct 90 ms 144376 KB Output is correct
18 Correct 103 ms 144372 KB Output is correct
19 Correct 96 ms 144448 KB Output is correct
20 Correct 103 ms 144360 KB Output is correct
21 Correct 96 ms 144332 KB Output is correct
22 Correct 95 ms 144284 KB Output is correct
23 Correct 102 ms 144416 KB Output is correct
24 Correct 104 ms 144388 KB Output is correct
25 Correct 88 ms 144356 KB Output is correct
26 Correct 98 ms 144376 KB Output is correct
27 Correct 90 ms 144296 KB Output is correct
28 Correct 87 ms 144312 KB Output is correct
29 Correct 178 ms 144480 KB Output is correct
30 Correct 381 ms 144644 KB Output is correct
31 Correct 440 ms 144788 KB Output is correct
32 Correct 547 ms 144656 KB Output is correct
33 Correct 584 ms 144652 KB Output is correct
34 Correct 442 ms 144736 KB Output is correct
35 Correct 405 ms 144668 KB Output is correct
36 Correct 458 ms 144688 KB Output is correct
37 Correct 346 ms 144808 KB Output is correct
38 Correct 262 ms 144644 KB Output is correct
39 Correct 495 ms 144672 KB Output is correct
40 Correct 535 ms 144672 KB Output is correct
41 Correct 490 ms 144592 KB Output is correct
42 Correct 467 ms 144776 KB Output is correct
43 Correct 169 ms 144588 KB Output is correct
44 Correct 162 ms 144644 KB Output is correct
45 Correct 165 ms 144740 KB Output is correct
46 Correct 156 ms 144656 KB Output is correct
47 Correct 503 ms 144716 KB Output is correct
48 Correct 480 ms 144716 KB Output is correct
49 Correct 463 ms 144624 KB Output is correct
50 Correct 422 ms 144676 KB Output is correct
51 Correct 536 ms 144844 KB Output is correct
52 Correct 500 ms 144664 KB Output is correct
53 Correct 464 ms 144660 KB Output is correct
54 Correct 411 ms 144784 KB Output is correct
55 Incorrect 241 ms 164804 KB Output isn't correct
56 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 144332 KB Output is correct
2 Correct 85 ms 144324 KB Output is correct
3 Correct 84 ms 144244 KB Output is correct
4 Correct 83 ms 144308 KB Output is correct
5 Correct 84 ms 144332 KB Output is correct
6 Correct 86 ms 144340 KB Output is correct
7 Correct 86 ms 144332 KB Output is correct
8 Correct 87 ms 144332 KB Output is correct
9 Correct 86 ms 144296 KB Output is correct
10 Correct 88 ms 144372 KB Output is correct
11 Correct 89 ms 144312 KB Output is correct
12 Correct 86 ms 144316 KB Output is correct
13 Correct 86 ms 144280 KB Output is correct
14 Correct 82 ms 144384 KB Output is correct
15 Correct 84 ms 144336 KB Output is correct
16 Correct 86 ms 144300 KB Output is correct
17 Correct 90 ms 144376 KB Output is correct
18 Correct 103 ms 144372 KB Output is correct
19 Correct 96 ms 144448 KB Output is correct
20 Correct 103 ms 144360 KB Output is correct
21 Correct 96 ms 144332 KB Output is correct
22 Correct 95 ms 144284 KB Output is correct
23 Correct 102 ms 144416 KB Output is correct
24 Correct 104 ms 144388 KB Output is correct
25 Correct 88 ms 144356 KB Output is correct
26 Correct 98 ms 144376 KB Output is correct
27 Correct 90 ms 144296 KB Output is correct
28 Correct 87 ms 144312 KB Output is correct
29 Correct 178 ms 144480 KB Output is correct
30 Correct 381 ms 144644 KB Output is correct
31 Correct 440 ms 144788 KB Output is correct
32 Correct 547 ms 144656 KB Output is correct
33 Correct 584 ms 144652 KB Output is correct
34 Correct 442 ms 144736 KB Output is correct
35 Correct 405 ms 144668 KB Output is correct
36 Correct 458 ms 144688 KB Output is correct
37 Correct 346 ms 144808 KB Output is correct
38 Correct 262 ms 144644 KB Output is correct
39 Correct 495 ms 144672 KB Output is correct
40 Correct 535 ms 144672 KB Output is correct
41 Correct 490 ms 144592 KB Output is correct
42 Correct 467 ms 144776 KB Output is correct
43 Correct 169 ms 144588 KB Output is correct
44 Correct 162 ms 144644 KB Output is correct
45 Correct 165 ms 144740 KB Output is correct
46 Correct 156 ms 144656 KB Output is correct
47 Correct 503 ms 144716 KB Output is correct
48 Correct 480 ms 144716 KB Output is correct
49 Correct 463 ms 144624 KB Output is correct
50 Correct 422 ms 144676 KB Output is correct
51 Correct 536 ms 144844 KB Output is correct
52 Correct 500 ms 144664 KB Output is correct
53 Correct 464 ms 144660 KB Output is correct
54 Correct 411 ms 144784 KB Output is correct
55 Incorrect 807 ms 176200 KB Output isn't correct
56 Halted 0 ms 0 KB -