oj.uz

Submission #290848

# Submission time Handle Problem Language Result Execution time Memory
290848 2020-09-04T13:49:36 Z crossing0ver Colors (RMI18_colors) C++17
100 / 100
 1150 ms 72652 KB 
#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(),A[i].clear(),B[i].clear();
	for (int i = 1; i <= 4*n; i++)
	 		t[i].clear();
	}

}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 25088 KB Output is correct
2 Correct 44 ms 25088 KB Output is correct
3 Correct 21 ms 25344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 25088 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 25088 KB Output is correct
2 Correct 49 ms 25088 KB Output is correct
3 Correct 22 ms 25216 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 25088 KB Output is correct
2 Correct 49 ms 25088 KB Output is correct
3 Correct 22 ms 25216 KB Output is correct
4 Correct 192 ms 25088 KB Output is correct
5 Correct 658 ms 42104 KB Output is correct
6 Correct 1150 ms 65756 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 25088 KB Output is correct
2 Correct 44 ms 25088 KB Output is correct
3 Correct 21 ms 25344 KB Output is correct
4 Correct 99 ms 25088 KB Output is correct
5 Correct 49 ms 25088 KB Output is correct
6 Correct 22 ms 25216 KB Output is correct
7 Correct 100 ms 25132 KB Output is correct
8 Correct 49 ms 25088 KB Output is correct
9 Correct 22 ms 25216 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 25404 KB Output is correct
2 Correct 624 ms 44688 KB Output is correct
3 Correct 650 ms 63720 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 25088 KB Output is correct
2 Correct 27 ms 25088 KB Output is correct
3 Correct 23 ms 25216 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 25088 KB Output is correct
2 Correct 44 ms 25088 KB Output is correct
3 Correct 21 ms 25344 KB Output is correct
4 Correct 74 ms 25088 KB Output is correct
5 Correct 99 ms 25088 KB Output is correct
6 Correct 49 ms 25088 KB Output is correct
7 Correct 22 ms 25216 KB Output is correct
8 Correct 192 ms 25088 KB Output is correct
9 Correct 658 ms 42104 KB Output is correct
10 Correct 1150 ms 65756 KB Output is correct
11 Correct 100 ms 25132 KB Output is correct
12 Correct 49 ms 25088 KB Output is correct
13 Correct 22 ms 25216 KB Output is correct
14 Correct 181 ms 25404 KB Output is correct
15 Correct 624 ms 44688 KB Output is correct
16 Correct 650 ms 63720 KB Output is correct
17 Correct 47 ms 25088 KB Output is correct
18 Correct 27 ms 25088 KB Output is correct
19 Correct 23 ms 25216 KB Output is correct
20 Correct 101 ms 27644 KB Output is correct
21 Correct 577 ms 46980 KB Output is correct
22 Correct 989 ms 72652 KB Output is correct