Submission #532246

#	Time	Username	Problem	Language	Result	Execution time	Memory
532246		Leonardo_Paes	Colors (RMI18_colors)	C++17	100 / 100	595 ms	69204 KiB

colors

#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 (stderr)

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 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22