oj.uz

Submission #290851

# Submission time Handle Problem Language Result Execution time Memory
290851 2020-09-04T13:51:11 Z crossing0ver Colors (RMI18_colors) C++17
100 / 100
 1130 ms 65480 KB 
#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

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

Subtask #1
15.0 / 15.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 25088 KB Output is correct
2 Correct 53 ms 25088 KB Output is correct
3 Correct 21 ms 25216 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 25088 KB Output is correct
2 Correct 53 ms 25088 KB Output is correct
3 Correct 21 ms 25216 KB Output is correct
4 Correct 208 ms 25336 KB Output is correct
5 Correct 636 ms 38856 KB Output is correct
6 Correct 1130 ms 58844 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 25248 KB Output is correct
2 Correct 44 ms 25088 KB Output is correct
3 Correct 20 ms 25344 KB Output is correct
4 Correct 114 ms 25088 KB Output is correct
5 Correct 53 ms 25088 KB Output is correct
6 Correct 21 ms 25216 KB Output is correct
7 Correct 101 ms 25088 KB Output is correct
8 Correct 50 ms 25208 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 25208 KB Output is correct
2 Correct 619 ms 39276 KB Output is correct
3 Correct 669 ms 56812 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 25248 KB Output is correct
2 Correct 44 ms 25088 KB Output is correct
3 Correct 20 ms 25344 KB Output is correct
4 Correct 73 ms 25088 KB Output is correct
5 Correct 114 ms 25088 KB Output is correct
6 Correct 53 ms 25088 KB Output is correct
7 Correct 21 ms 25216 KB Output is correct
8 Correct 208 ms 25336 KB Output is correct
9 Correct 636 ms 38856 KB Output is correct
10 Correct 1130 ms 58844 KB Output is correct
11 Correct 101 ms 25088 KB Output is correct
12 Correct 50 ms 25208 KB Output is correct
13 Correct 22 ms 25216 KB Output is correct
14 Correct 181 ms 25208 KB Output is correct
15 Correct 619 ms 39276 KB Output is correct
16 Correct 669 ms 56812 KB Output is correct
17 Correct 46 ms 25088 KB Output is correct
18 Correct 27 ms 25088 KB Output is correct
19 Correct 22 ms 25216 KB Output is correct
20 Correct 100 ms 25088 KB Output is correct
21 Correct 585 ms 41208 KB Output is correct
22 Correct 957 ms 65480 KB Output is correct