oj.uz

Submission #532242

# Submission time Handle Problem Language Result Execution time Memory
532242 2022-03-02T14:45:15 Z Leonardo_Paes Colors (RMI18_colors) C++17
100 / 100
 703 ms 69464 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[1<<19];
public:
	void build(int node, int tl, int tr){ 
		tree[node].clear();
		if(tl == tr) return;
		int mid = (tl + tr) >> 1;
		build(2*node, tl, mid); build(2*node+1, mid+1, tr);
	}
	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(1, 1, 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:77:11: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   77 |   for(pii p : tree[node]) dsu.rollback();
      |           ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19984 KB Output is correct
2 Correct 33 ms 20036 KB Output is correct
3 Correct 14 ms 20112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 20088 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 19964 KB Output is correct
2 Correct 34 ms 19980 KB Output is correct
3 Correct 15 ms 20032 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 19964 KB Output is correct
2 Correct 34 ms 19980 KB Output is correct
3 Correct 15 ms 20032 KB Output is correct
4 Correct 156 ms 19980 KB Output is correct
5 Correct 402 ms 35360 KB Output is correct
6 Correct 703 ms 54928 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19984 KB Output is correct
2 Correct 33 ms 20036 KB Output is correct
3 Correct 14 ms 20112 KB Output is correct
4 Correct 72 ms 19964 KB Output is correct
5 Correct 34 ms 19980 KB Output is correct
6 Correct 15 ms 20032 KB Output is correct
7 Correct 89 ms 19980 KB Output is correct
8 Correct 35 ms 20016 KB Output is correct
9 Correct 15 ms 19916 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 20004 KB Output is correct
2 Correct 390 ms 36368 KB Output is correct
3 Correct 410 ms 45636 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 20064 KB Output is correct
2 Correct 22 ms 20400 KB Output is correct
3 Correct 16 ms 19984 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19984 KB Output is correct
2 Correct 33 ms 20036 KB Output is correct
3 Correct 14 ms 20112 KB Output is correct
4 Correct 87 ms 20088 KB Output is correct
5 Correct 72 ms 19964 KB Output is correct
6 Correct 34 ms 19980 KB Output is correct
7 Correct 15 ms 20032 KB Output is correct
8 Correct 156 ms 19980 KB Output is correct
9 Correct 402 ms 35360 KB Output is correct
10 Correct 703 ms 54928 KB Output is correct
11 Correct 89 ms 19980 KB Output is correct
12 Correct 35 ms 20016 KB Output is correct
13 Correct 15 ms 19916 KB Output is correct
14 Correct 130 ms 20004 KB Output is correct
15 Correct 390 ms 36368 KB Output is correct
16 Correct 410 ms 45636 KB Output is correct
17 Correct 39 ms 20064 KB Output is correct
18 Correct 22 ms 20400 KB Output is correct
19 Correct 16 ms 19984 KB Output is correct
20 Correct 107 ms 20308 KB Output is correct
21 Correct 373 ms 38804 KB Output is correct
22 Correct 674 ms 69464 KB Output is correct