Submission #290842

#	Time	Username	Problem	Language	Result	Execution time	Memory
290842		crossing0ver	Colors (RMI18_colors)	C++17	0 / 100	3088 ms	26944 KiB

colors

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
const int N = 1.5e5+5;
int n,m,a[N],b[N],ans,sz[N],P[N];
vi adj[N],t[4*N],A[N],B[N];
void upd(int v,int tl,int tr,int l,int r,int id) {
	if (l > tr || r < tl) return;
	if (l <= tl && tr <= r) {
		t[v].pb(id);
	//	join(v,tl,tr);
	}else {
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,id);
		upd(v*2+1,tm+1,tr,l,r,id);
	} 
}

bool in[N];
int timer,h[N];
int par(int a) {
	if (a == P[a]) return a;
	return par(P[a]);
}

int *Q[20000000];
int val[20000000];
void change(int &x,int VAL) {
	timer++;
	Q[timer] = &x;
	val[timer] = x;
	x = VAL;
}
void rollback() {
	(*Q[timer]) = val[timer];
	timer--;
}
void join(int x,int y) {
	x = par(x);
	y = par(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x,y);
	change(sz[x],sz[x] + sz[y]);
	change(P[y],x);
	
}
void dfs(int v,int tl,int tr) {
	int enter_time = timer;
	for (int i : t[v]) {
		in[i] = 1;
	//	for (int j : adj[i])
		//	if (in[j]) join(i,j);
	}
	if (tl == tr) {
		for (int x : A[tl])
		//	if (in[x])
			 h[par(x)] = 1;
		for (int x : B[tl]) 
		//	if (in[x]) {
				if (h[par(x)] == 0) {
					ans = 0;
			//	}
			}
			for (int x : A[tl])	h[par(x)] = 0;	
	}
	else {
	int tm = (tl + tr)/2;
	dfs(v*2,tl,tm);
	dfs(v*2+1,tm+1,tr);
}
	while(enter_time != timer) {
		rollback();
	}
	for (int i : t[v])
		in[i] = 0;
}
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		P[i] = i;
	}
	for (int i = 1; i <= n; i++)
		cin >> a[i], A[a[i]].pb(i);
	for (int i = 1; i <= n; i++)
		cin >> b[i],B[b[i]].pb(i);
	for (int i = 0,a,b;i < m; i++) {
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] < b[i]) {
			cout << "0\n";
			return;
		}
	}
	for (int i = 1; i <= n; i++) {
		upd(1,1,n,b[i],a[i],i);
	}
	ans = 1;
	dfs(1,1,n);
	cout << ans << '\n';
	return;
	
	vector<pii> g(n);
	for (int i = 1; i <= n; i++)
		g[i-1] = {b[i],i};
	sort(g.rbegin(),g.rend());
	for (auto i1 : g) {
		int v = i1.se;
		int target = i1.fi;
		if (a[v] == target) continue;
		queue<int> q;
		q.push(v);
		bool flag = 0;
		vector<bool> vis(n+1);
		vis[v] = 1;
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			if (a[v] == target) {
				flag = 1;
				break;
			}
			for (int i : adj[v]) 
				if (a[i] >= target && b[i] <= target && !vis[i]) {
					q.push(i);
					vis[i] = 1;
				} 
		}
		if (flag == 0) {
			cout <<"0\n";
			return;
		}
	}
	cout <<"1\n";
}
main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt;
	cin >> tt;
	while(tt--) {
		solve();
		// clear
	for (int i = 1; i <= n; i++)
		adj[i].clear();
	for (int i = 1; i <= 4*n; i++)
	 		t[i].clear();
	}

}

Compilation message (stderr)

colors.cpp:145:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main() {
      |      ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22