oj.uz

Submission #532246

# Submission time Handle Problem Language Result Execution time Memory
532246 2022-03-02T14:50:44 Z Leonardo_Paes Colors (RMI18_colors) C++17
100 / 100
 595 ms 69204 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 n){ for(int i=1; i<=(1<<(2+(31-__builtin_clz(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 62 ms 19660 KB Output is correct
2 Correct 29 ms 19736 KB Output is correct
3 Correct 13 ms 20044 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19836 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19700 KB Output is correct
2 Correct 32 ms 19744 KB Output is correct
3 Correct 15 ms 19876 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19700 KB Output is correct
2 Correct 32 ms 19744 KB Output is correct
3 Correct 15 ms 19876 KB Output is correct
4 Correct 133 ms 19728 KB Output is correct
5 Correct 363 ms 35116 KB Output is correct
6 Correct 595 ms 54692 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 19660 KB Output is correct
2 Correct 29 ms 19736 KB Output is correct
3 Correct 13 ms 20044 KB Output is correct
4 Correct 69 ms 19700 KB Output is correct
5 Correct 32 ms 19744 KB Output is correct
6 Correct 15 ms 19876 KB Output is correct
7 Correct 68 ms 19660 KB Output is correct
8 Correct 35 ms 19752 KB Output is correct
9 Correct 14 ms 19944 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 19660 KB Output is correct
2 Correct 354 ms 36112 KB Output is correct
3 Correct 365 ms 45540 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 19800 KB Output is correct
2 Correct 22 ms 20056 KB Output is correct
3 Correct 15 ms 19880 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 19660 KB Output is correct
2 Correct 29 ms 19736 KB Output is correct
3 Correct 13 ms 20044 KB Output is correct
4 Correct 69 ms 19836 KB Output is correct
5 Correct 69 ms 19700 KB Output is correct
6 Correct 32 ms 19744 KB Output is correct
7 Correct 15 ms 19876 KB Output is correct
8 Correct 133 ms 19728 KB Output is correct
9 Correct 363 ms 35116 KB Output is correct
10 Correct 595 ms 54692 KB Output is correct
11 Correct 68 ms 19660 KB Output is correct
12 Correct 35 ms 19752 KB Output is correct
13 Correct 14 ms 19944 KB Output is correct
14 Correct 123 ms 19660 KB Output is correct
15 Correct 354 ms 36112 KB Output is correct
16 Correct 365 ms 45540 KB Output is correct
17 Correct 38 ms 19800 KB Output is correct
18 Correct 22 ms 20056 KB Output is correct
19 Correct 15 ms 19880 KB Output is correct
20 Correct 96 ms 19948 KB Output is correct
21 Correct 367 ms 38792 KB Output is correct
22 Correct 571 ms 69204 KB Output is correct