| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 768827 |
2023-06-28T17:34:55 Z |
oyber |
Joker (BOI20_joker) |
C++14 |
|
79 ms |
12296 KB |
#pragma GCC optimize("O3")
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <stack>
using namespace std;
vector<int> u;
vector<int> s;
vector<int> p;
int find(int n) {
if (u[n] == n) return n;
return find(u[n]);
}
int find_compress2(int n) {
int r = n;
int z = p[r];
while (r != u[r]) {
r = u[r];
z ^= p[r];
}
while (n != r) {
if (p[u[n]] != z) p[n] = !p[n];
z ^= p[n];
int next_n = u[n];
u[n] = r;
n = next_n;
}
return r;
}
int find_compress(int n) {
if (u[n] == n) return n;
int r = find_compress(u[n]);
if (p[u[n]] != p[r]) p[n] = !p[n];
u[n] = r;
return u[n];
}
int parity(int n) {
if (u[n] == n) return 0;
return parity(u[n])^p[n];
}
struct UniteInfo {
int a;
int b;
};
UniteInfo unite(int a, int b) {
int ap = find(a);
int bp = find(b);
if (s[bp] > s[ap]) {
swap(a, b);
swap(ap, bp);
}
u[bp] = ap;
s[ap] += s[bp];
if (parity(a) == parity(b)) {
p[bp] = 1;
} else {
p[bp] = 0;
}
return UniteInfo {
ap,
bp,
};
}
void undo(UniteInfo info) {
u[info.b] = info.b;
s[info.a] -= s[info.b];
p[info.b] = 0;
}
struct Query {
int l;
int r;
int i;
};
bool comp_query(Query q1, Query q2) {
return q1.r > q2.r;
}
bool comp_query2(Query q1, Query q2) {
return q1.l < q2.l;
}
int main() {
int n, m, qn;
scanf("%d %d %d", &n, &m, &qn);
u.resize(n);
s.resize(n, 1);
p.resize(n);
vector<pair<int, int>> e(m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--;b--;
e[i] = make_pair(a, b);
//printf("%d %d %d\n", a, b, i);
}
vector<Query> q(qn);
for (int i = 0; i < qn; i++) {
int l, r;
scanf("%d %d", &l, &r);
l--;r--;
q[i] = Query{l,r,i};
}
sort(q.begin(), q.end(), comp_query2);
int group_size = 1024;
int group_num = q[q.size()-1].l / group_size + 1;
//printf("%d %d\n", int(q[q.size()-1].l), group_num);
vector<vector<Query>> groups(group_num);
vector<int> min_l(group_num, 1000000);
//printf("n: %d\n", group_num);
int j = 0;
for (int i = 0; i < group_num; i++) {
while (j < qn) {
if (q[j].l >= (i+1)*group_size) break;
groups[i].push_back(q[j]);
min_l[i] = min(min_l[i], q[j].l);
//printf("g: %d q: %d\n", i, q[j].i);
j++;
}
sort(groups[i].begin(), groups[i].end(), comp_query);
//printf("%d\n", min_l[i]);
}
vector<UniteInfo> infos;
vector<bool> result(qn);
for (int j = 0; j < group_num; j++) {
if (groups[j].size() == 0) continue;;
//reset state
for (int i = 0; i < n; i++) {
u[i] = i;
s[i] = 1;
p[i] = 0;
}
bool l_cycle = false;
int current_l = 0;
for (; current_l < min_l[j]; current_l++) {
int a = e[current_l].first;
int b = e[current_l].second;
//printf("%d %d %d\n", current_l, a, b);
//printf("(%d %d) (%d %d)\n", find_compress(a), find_compress(b), find_compress2(a), find_compress2(b));
if (find_compress2(a) == find_compress2(b)) {
if (parity(a) == parity(b)) {
l_cycle = true;
break;
}
} else {
unite(a, b);
}
}
//printf("l: %d\n", current_l);
int current_r = m-1;
bool r_cycle = false;
for (int i = 0; i < int(groups[j].size()); i++) {
if (r_cycle || l_cycle) {
result[groups[j][i].i] = true;
continue;
}
int l = groups[j][i].l;
int r = groups[j][i].r;
//printf("%d: %d %d\n", i, l, r);
while (current_r > r) {
int a = e[current_r].first;
int b = e[current_r].second;
//printf("%d %d %d\n", current_r, a, b);
/*int y1 = find_compress(a);
int z1 = find_compress(b);
int y2 = find_compress2(a);
int z2 = find_compress2(b);
if (y1 != y2 || z1 != z2) {
printf("(%d %d) (%d %d)\n", y1, z1, y2, z2);
}*/
if (find_compress2(a) == find_compress2(b)) {
if (parity(a) == parity(b)) {
r_cycle = true;
break;
}
} else {
unite(a, b);
}
current_r--;
}
if (r_cycle) {
result[groups[j][i].i] = true;
continue;
}
bool cycle = false;
for (int c_l = current_l; c_l < l; c_l++) {
int a = e[c_l].first;
int b = e[c_l].second;
//printf("%d %d %d\n", current_l, a, b);
if (find(a) == find(b)) {
if (parity(a) == parity(b)) {
cycle = true;
break;
}
} else {
infos.push_back(unite(a, b));
}
}
if (cycle) {
result[groups[j][i].i] = true;
}
while (infos.size() > 0) {
undo(infos.back());
infos.pop_back();
}
}
}
for (int i = 0; i < qn; i++) {
if (result[i]) {
printf("YES\n");
} else {
printf("NO\n");
}
}
}
Compilation message
Joker.cpp: In function 'int main()':
Joker.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d %d %d", &n, &m, &qn);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
Joker.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
1 ms |
288 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
1 ms |
288 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
78 ms |
10992 KB |
Output is correct |
| 4 |
Incorrect |
79 ms |
12296 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
1 ms |
288 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
1 ms |
288 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
1 ms |
288 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
