Submission #290851

#	Time	Username	Problem	Language	Result	Execution time	Memory
290851		crossing0ver	Colors (RMI18_colors)	C++17	100 / 100	1130 ms	65480 KiB

colors

#include<bits/stdc++.h>
#define pb push_back
#define vi vector<int>
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);
	}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])
			 h[par(x)] = 1;
		for (int x : B[tl]) 
				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';
}
main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt;
	cin >> tt;
	while(tt--) {
		solve();
	for (int i = 1; i <= n; i++)
		adj[i].clear(),A[i].clear(),B[i].clear();
	for (int i = 1; i <= 4*n; i++)
	 		t[i].clear();
	}

}

Compilation message (stderr)

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

• 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