oj.uz

Submission #530188

# Submission time Handle Problem Language Result Execution time Memory
530188 2022-02-24T18:52:00 Z LucaDantas Colors (RMI18_colors) C++17
100 / 100
 631 ms 88464 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e5+10;

struct DSU {
	int pai[maxn], peso[maxn], t;
	struct SV { int a, b, peso_a, peso_b; };
	
	vector<SV> sv;

	/* void init(int n) {
		for(int i = 0; i <= n; i++)
			pai[i] = i, peso[i] = 1;
		sv.clear();
		t = 0;
	} */
	DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	
	int find(int x) { return pai[x] == x ? x : find(pai[x]); }

	void join(int a, int b) {
		a = find(a), b = find(b);

		if(peso[a] < peso[b])
			swap(a, b);
		
		++t;
		sv.push_back({a, b, peso[a], peso[b]});

		if(a == b) return;

		pai[b] = a;
		peso[a] += peso[b];
	}
	void rollback(int voltar) {
		while(t > voltar) {
			--t;
			auto [a, b, peso_a, peso_b] = sv.back();
			sv.pop_back();
			pai[a] = a, pai[b] = b;
			peso[a] = peso_a, peso[b] = peso_b;
		}
	}
} dsu;

int a[maxn], b[maxn];

vector<int> posA[maxn], posB[maxn];

int ans = 1;

struct SegmentTree {
	vector<pair<int,int>> tree[4*maxn];
	void addEdge(int node, int i, int j, int l, int r, pair<int,int> e) {
		if(i > r || j < l) return;
		if(i >= l && j <= r) return (void)(tree[node].push_back(e));
		int m = (i+j) >> 1;
		addEdge(node<<1, i, m, l, r, e);
		addEdge(node<<1|1, m+1, j, l, r, e);
	}
	void go(int node, int i, int j) {
		int voltar = dsu.t;
		for(auto e : tree[node])
			dsu.join(e.first, e.second);

		if(i == j) {
			vector<int> ids;
			for(int x : posA[i]) // salvo as componentes no grafo atual de cada um dos caras que tem a[i] == query atual
				ids.push_back(dsu.find(x));
			sort(ids.begin(), ids.end());

			for(int x : posB[i])
				ans &= binary_search(ids.begin(), ids.end(), dsu.find(x));

			dsu.rollback(voltar);
			return;
		}

		int m = (i+j) >> 1;
		go(node<<1, i, m); // ele da roolback sozinho pra voltar como recebeu
		go(node<<1|1, m+1, j);

		dsu.rollback(voltar);
	}
} seg;

void clean(int n, int m) {
	dsu.rollback(0);

	for(int i = 1; i <= n; i++)
		posA[i].clear(), posB[i].clear(), a[i] = 0, b[i] = 0;

	ans = 1;

	for(int i = 1; i <= 4*n; i++)
		seg.tree[i].clear();
}

int main() {
	int t; scanf("%d", &t);
	while(t--) {
		int n, m; scanf("%d %d", &n, &m);
		for(int i = 1; i <= n; i++)
			scanf("%d", a+i), posA[a[i]].push_back(i);
		for(int i = 1; i <= n; i++)
			scanf("%d", b+i), posB[b[i]].push_back(i);

		bool ruim = 0;
		for(int i = 1; i <= n; i++)
			if(a[i] < b[i]) { ruim = 1; }

		for(int i = 0; i < m; i++) {
			int x, y; scanf("%d %d", &x, &y);
			
			if(b[x] > b[y])
				swap(x, y);

			if(!ruim && a[x] >= b[y])
				seg.addEdge(1, 1, n, b[y], min(a[x], a[y]), {x, y});
		}

		if(ruim) { puts("0"); clean(n, m); continue; }

		seg.go(1, 1, n);

		printf("%d\n", ans);

		clean(n, m);
	}
}

Compilation message

colors.cpp: In function 'int main()':
colors.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  int t; scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~
colors.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   int n, m; scanf("%d %d", &n, &m);
      |             ~~~~~^~~~~~~~~~~~~~~~~
colors.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%d", a+i), posA[a[i]].push_back(i);
      |    ~~~~~^~~~~~~~~~~
colors.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d", b+i), posB[b[i]].push_back(i);
      |    ~~~~~^~~~~~~~~~~
colors.cpp:114:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |    int x, y; scanf("%d %d", &x, &y);
      |              ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 30072 KB Output is correct
2 Correct 39 ms 30560 KB Output is correct
3 Correct 18 ms 30392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 30228 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 30028 KB Output is correct
2 Correct 40 ms 30556 KB Output is correct
3 Correct 19 ms 30212 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 30028 KB Output is correct
2 Correct 40 ms 30556 KB Output is correct
3 Correct 19 ms 30212 KB Output is correct
4 Correct 162 ms 33136 KB Output is correct
5 Correct 430 ms 51692 KB Output is correct
6 Correct 631 ms 71200 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 30072 KB Output is correct
2 Correct 39 ms 30560 KB Output is correct
3 Correct 18 ms 30392 KB Output is correct
4 Correct 87 ms 30028 KB Output is correct
5 Correct 40 ms 30556 KB Output is correct
6 Correct 19 ms 30212 KB Output is correct
7 Correct 85 ms 31556 KB Output is correct
8 Correct 40 ms 30608 KB Output is correct
9 Correct 19 ms 30364 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 30200 KB Output is correct
2 Correct 377 ms 52588 KB Output is correct
3 Correct 391 ms 62256 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 30156 KB Output is correct
2 Correct 28 ms 30752 KB Output is correct
3 Correct 22 ms 30308 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 30072 KB Output is correct
2 Correct 39 ms 30560 KB Output is correct
3 Correct 18 ms 30392 KB Output is correct
4 Correct 84 ms 30228 KB Output is correct
5 Correct 87 ms 30028 KB Output is correct
6 Correct 40 ms 30556 KB Output is correct
7 Correct 19 ms 30212 KB Output is correct
8 Correct 162 ms 33136 KB Output is correct
9 Correct 430 ms 51692 KB Output is correct
10 Correct 631 ms 71200 KB Output is correct
11 Correct 85 ms 31556 KB Output is correct
12 Correct 40 ms 30608 KB Output is correct
13 Correct 19 ms 30364 KB Output is correct
14 Correct 164 ms 30200 KB Output is correct
15 Correct 377 ms 52588 KB Output is correct
16 Correct 391 ms 62256 KB Output is correct
17 Correct 48 ms 30156 KB Output is correct
18 Correct 28 ms 30752 KB Output is correct
19 Correct 22 ms 30308 KB Output is correct
20 Correct 117 ms 32808 KB Output is correct
21 Correct 376 ms 55488 KB Output is correct
22 Correct 603 ms 88464 KB Output is correct