#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
colors.cpp:145:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
145 | main() {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
26484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
25256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
26616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
26616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
26484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
28012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
25216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
26484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
