| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261764 |
2020-08-12T04:37:31 Z |
shenxy |
Colors (RMI18_colors) |
C++11 |
|
803 ms |
110672 KB |
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
int N;
vector<int> queries[150000];
bool sad = 0;
struct UFDS {
vector<int> parent, sz;
vector<ii> ops;
UFDS(int N) {
for (int i = 0; i < N; ++i) parent.push_back(i), sz.push_back(1);
}
int find_parent(int i) {
if (parent[i] == i) return i;
return find_parent(parent[i]);
}
void union_set(int p, int q) {
p = find_parent(p), q = find_parent(q);
if (p == q) {
ops.push_back(ii(-1, -1));
return;
}
if (sz[p] < sz[q]) swap(p, q);
parent[q] = p, sz[p] += sz[q];
ops.push_back(ii(p, q));
}
void rollback() {
if (ops.back() == ii(-1, -1)) return;
parent[ops.back().second] = ops.back().second;
sz[ops.back().first] -= sz[ops.back().second];
ops.pop_back();
}
} *sets;
struct seg {
int s, e, m;
vector<ii> v;
seg *l, *r;
seg(int _s, int _e) {
s = _s, e = _e, m = (s + e) / 2;
if (s != e) {
l = new seg(s, m);
r = new seg(m + 1, e);
}
}
void add_edge(int a, int b, ii edge) {
if (s == a && e == b) v.push_back(edge);
else if (a > m) r -> add_edge(a, b, edge);
else if (b <= m) l -> add_edge(a, b, edge);
else l -> add_edge(a, m, edge), r -> add_edge(m + 1, b, edge);
}
void query() {
for (ii i: v) sets -> union_set(i.first, i.second);
if (s == e) {
for (int i: queries[s]) {
if (sets -> find_parent(i) != sets -> find_parent(N + s)) sad = 1;
}
} else {
l -> query();
r -> query();
}
for (int i = 0; i < v.size(); ++i) sets -> rollback();
}
} *root;
int main() {
int T;
scanf("%d", &T);
for (int h = 0; h < T; ++h) {
sad = 0;
int M;
scanf("%d %d", &N, &M);
int A[N], B[N], u, v;
for (int i = 0; i < N; ++i) queries[i].clear();
for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
for (int i = 0; i < N; ++i) scanf("%d", &B[i]);
for (int i = 0; i < N; ++i) --A[i], --B[i];
sets = new UFDS(2 * N);
root = new seg(0, N - 1);
for (int i = 0; i < N; ++i) {
if (A[i] < B[i]) sad = 1;
else root -> add_edge(B[i], A[i], ii(i, N + A[i]));
queries[B[i]].push_back(i);
}
for (int i = 0; i < M; ++i) {
scanf("%d %d", &u, &v);
--u, --v;
int low = max(B[u], B[v]), high = min(A[u], A[v]);
if (low <= high) root -> add_edge(low, high, ii(u, v));
}
root -> query();
printf(sad ? "0\n" : "1\n");
}
return 0;
}
Compilation message
colors.cpp: In member function 'void seg::query()':
colors.cpp:63:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); ++i) sets -> rollback();
~~^~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &T);
~~~~~^~~~~~~~~~
colors.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
colors.cpp:75:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
~~~~~^~~~~~~~~~~~~
colors.cpp:76:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; ++i) scanf("%d", &B[i]);
~~~~~^~~~~~~~~~~~~
colors.cpp:86:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
39544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
18168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
40184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
40184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
39544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
339 ms |
73836 KB |
Output is correct |
| 2 |
Correct |
768 ms |
110672 KB |
Output is correct |
| 3 |
Correct |
803 ms |
97152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
12152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
39544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
