oj.uz

Submission #261772

# Submission time Handle Problem Language Result Execution time Memory
261772 2020-08-12T04:45:08 Z shenxy Colors (RMI18_colors) C++11
100 / 100
 1036 ms 106832 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)) {
			ops.pop_back();
			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(A[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:66: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:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &T);
  ~~~~~^~~~~~~~~~
colors.cpp:75: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:78: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:79: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:89:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &v);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 34424 KB Output is correct
2 Correct 52 ms 14328 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 14456 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 34636 KB Output is correct
2 Correct 58 ms 14460 KB Output is correct
3 Correct 9 ms 4992 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 34636 KB Output is correct
2 Correct 58 ms 14460 KB Output is correct
3 Correct 9 ms 4992 KB Output is correct
4 Correct 313 ms 67116 KB Output is correct
5 Correct 642 ms 83788 KB Output is correct
6 Correct 1036 ms 104432 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 34424 KB Output is correct
2 Correct 52 ms 14328 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 164 ms 34636 KB Output is correct
5 Correct 58 ms 14460 KB Output is correct
6 Correct 9 ms 4992 KB Output is correct
7 Correct 157 ms 34812 KB Output is correct
8 Correct 60 ms 14328 KB Output is correct
9 Correct 9 ms 5120 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 67400 KB Output is correct
2 Correct 597 ms 85236 KB Output is correct
3 Correct 594 ms 75988 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10132 KB Output is correct
2 Correct 21 ms 5948 KB Output is correct
3 Correct 11 ms 5120 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 34424 KB Output is correct
2 Correct 52 ms 14328 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 109 ms 14456 KB Output is correct
5 Correct 164 ms 34636 KB Output is correct
6 Correct 58 ms 14460 KB Output is correct
7 Correct 9 ms 4992 KB Output is correct
8 Correct 313 ms 67116 KB Output is correct
9 Correct 642 ms 83788 KB Output is correct
10 Correct 1036 ms 104432 KB Output is correct
11 Correct 157 ms 34812 KB Output is correct
12 Correct 60 ms 14328 KB Output is correct
13 Correct 9 ms 5120 KB Output is correct
14 Correct 308 ms 67400 KB Output is correct
15 Correct 597 ms 85236 KB Output is correct
16 Correct 594 ms 75988 KB Output is correct
17 Correct 56 ms 10132 KB Output is correct
18 Correct 21 ms 5948 KB Output is correct
19 Correct 11 ms 5120 KB Output is correct
20 Correct 160 ms 22648 KB Output is correct
21 Correct 660 ms 76836 KB Output is correct
22 Correct 949 ms 106832 KB Output is correct