oj.uz

Submission #532247

# Submission time Handle Problem Language Result Execution time Memory
532247 2022-03-02T14:51:35 Z Leonardo_Paes Colors (RMI18_colors) C++17
100 / 100
 697 ms 71116 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define f first
#define s second
const int maxn = 1e5 + 5e4 + 10;

int n, m, a[maxn], b[maxn];
vector<int> sexo[maxn], q[maxn];
bool ans;

struct edge{
	int l, r, u, v;
	edge():l(0), r(0), u(0), v(0){}
	edge(int l, int r, int u, int v):l(l), r(r), u(u), v(v){}
};

class DSU{
private:
	int pai[maxn], sz[maxn];
	bool ok[maxn];
	stack<pii> s;
public:
	void init(int n){ for(int i=1; i<=n; i++) pai[i] = i, sz[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(a == b){
			s.push({0, 0});
			return;
		}
		if(sz[a] > sz[b]) swap(a, b);
		pai[a] = b;
		sz[b] += sz[a];
		s.push({a, b});
	}
	void rollback(){
		int a = s.top().f, b = s.top().s;
		s.pop();
		pai[a] = a;
		sz[b] -= sz[a];
	}
	void att(int x, bool v){ ok[find(x)] = v; }
	bool query(int x){ return ok[find(x)]; }
}dsu;

class SEG{
private:
	vector<pii> tree[4*maxn];
public:
	void build(int n){ for(int i=1; i<=4*n; i++) tree[i].clear(); }
	void update(int node, int tl, int tr, edge e){
		if(tl > e.r or tr < e.l) return;
		if(tl >= e.l and tr <= e.r){
			tree[node].push_back({e.u, e.v});
			return;
		}
		int mid = (tl + tr) >> 1;
		update(2*node, tl, mid, e); update(2*node+1, mid+1, tr, e);
	}
	void solve(int node, int tl, int tr){
		for(pii p : tree[node]) dsu.join(p.f, p.s);
		if(tl == tr){
			for(int x : sexo[tl]) dsu.att(x, 1);
			for(int x : q[tl]) ans &= dsu.query(x);
			for(int x : sexo[tl]) dsu.att(x, 0);
		}
		else{
			int mid = (tl + tr) >> 1;
			solve(2*node, tl, mid); solve(2*node+1, mid+1, tr);
		}
		for(pii p : tree[node]) dsu.rollback();
	}
}seg;

void reset(){
	dsu.init(n);
	seg.build(n);
	for(int i=1; i<=n; i++) sexo[i].clear(), q[i].clear();
	ans = 1;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t;
	cin >> t;
	while(t--){
		cin >> n >> m;
		for(int i=1; i<=n; i++) cin >> a[i];
		for(int i=1; i<=n; i++) cin >> b[i];
		reset();
		for(int i=1; i<=n; i++){
			if(a[i] < b[i]) ans = 0;
			q[b[i]].push_back(i);
			sexo[a[i]].push_back(i);
		}
		for(int i=1; i<=m; i++){
			int u, v;
			cin >> u >> v;
			int r = min(a[u], a[v]), l = max(b[u], b[v]);
			if(l > r) continue;
			edge e(l, r, u, v);
			seg.update(1, 1, n, e);
		}
		seg.solve(1, 1, n);
		cout << ans << "\n";
	}
	return 0;
}

Compilation message

colors.cpp: In member function 'void SEG::solve(int, int, int)':
colors.cpp:72:11: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   72 |   for(pii p : tree[node]) dsu.rollback();
      |           ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 21496 KB Output is correct
2 Correct 40 ms 21524 KB Output is correct
3 Correct 15 ms 21708 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 21704 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21572 KB Output is correct
2 Correct 36 ms 21452 KB Output is correct
3 Correct 19 ms 21732 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21572 KB Output is correct
2 Correct 36 ms 21452 KB Output is correct
3 Correct 19 ms 21732 KB Output is correct
4 Correct 146 ms 21512 KB Output is correct
5 Correct 422 ms 36852 KB Output is correct
6 Correct 697 ms 56420 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 21496 KB Output is correct
2 Correct 40 ms 21524 KB Output is correct
3 Correct 15 ms 21708 KB Output is correct
4 Correct 84 ms 21572 KB Output is correct
5 Correct 36 ms 21452 KB Output is correct
6 Correct 19 ms 21732 KB Output is correct
7 Correct 73 ms 21488 KB Output is correct
8 Correct 33 ms 21432 KB Output is correct
9 Correct 15 ms 21700 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 21532 KB Output is correct
2 Correct 431 ms 37940 KB Output is correct
3 Correct 385 ms 47208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 21568 KB Output is correct
2 Correct 29 ms 21824 KB Output is correct
3 Correct 17 ms 21580 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 21496 KB Output is correct
2 Correct 40 ms 21524 KB Output is correct
3 Correct 15 ms 21708 KB Output is correct
4 Correct 74 ms 21704 KB Output is correct
5 Correct 84 ms 21572 KB Output is correct
6 Correct 36 ms 21452 KB Output is correct
7 Correct 19 ms 21732 KB Output is correct
8 Correct 146 ms 21512 KB Output is correct
9 Correct 422 ms 36852 KB Output is correct
10 Correct 697 ms 56420 KB Output is correct
11 Correct 73 ms 21488 KB Output is correct
12 Correct 33 ms 21432 KB Output is correct
13 Correct 15 ms 21700 KB Output is correct
14 Correct 132 ms 21532 KB Output is correct
15 Correct 431 ms 37940 KB Output is correct
16 Correct 385 ms 47208 KB Output is correct
17 Correct 55 ms 21568 KB Output is correct
18 Correct 29 ms 21824 KB Output is correct
19 Correct 17 ms 21580 KB Output is correct
20 Correct 99 ms 21948 KB Output is correct
21 Correct 355 ms 40460 KB Output is correct
22 Correct 634 ms 71116 KB Output is correct