#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
vector<int> aList[150005];
vector<int> bList[150005];
int a[150005];
int b[150005];
ii EdgeList[150005];
pair<ii, ii> EdgeList2[150005];
int N, M, P;
vector<ii> edges[5+(1<<19)];
void init(int i = 1, int s = 1, int e = N){
int l = (i<<1);
int r = (i<<1)|1;
int m = (s+e)>>1;
edges[i] = vector<ii>();
if(s == e){
}else{
init(l, s, m);
init(r, m+1, e);
}
}
void addEdge(int u, int v, int x, int y, int i = 1, int s = 1, int e = N){
if(x <= s && e <= y){
//printf("addEdge(%d, %d, %d, %d, %d, %d, %d)\n", u, v, x, y, i, s, e);
edges[i].push_back(ii(u, v));
return;
}else{
int l = (i<<1);
int r = (i<<1)|1;
int m = (s+e)>>1;
if(y <= m){
addEdge(u, v, x, y, l, s, m);
}else if(x > m){
addEdge(u, v, x, y, r, m+1, e);
}else{
addEdge(u, v, x, y, l, s, m);
addEdge(u, v, x, y, r, m+1, e);
}
}
}
int p[150005];
int rank1[150005];
stack<iii> pChanges;
stack<iii> rank1Changes;
void init1(int N){
pChanges = stack<iii>();
rank1Changes = stack<iii>();
for(int i = 1; i <= N; i ++){
p[i] = i;
rank1[i] = 0;
}
}
int findSet(int i){
return (p[i] == i) ? i : findSet(p[i]);
}
//set<int> changed;
void unionSet(int u, int v, int t){
int x = findSet(u);
int y = findSet(v);
if(x != y){
if(rank1[x] > rank1[y]){
pChanges.push(iii(y, p[y], t));
p[y] = x;
}else{
pChanges.push(iii(x, p[x], t));
p[x] = y;
if(rank1[x] == rank1[y]){
rank1Changes.push(iii(y, p[y], t));
rank1[y] ++;
}
}
}
}
void rollback(int t){
while(!pChanges.empty()){
int x, val, t1;
tie(x, val, t1) = pChanges.top();
if(t1 < t){break;}
p[x] = val;
pChanges.pop();
}
while(!rank1Changes.empty()){
int x, val, t1;
tie(x, val, t1) = rank1Changes.top();
if(t1 < t){break;}
rank1[x] = val;
rank1Changes.pop();
}
}
bool satisfied[150005];
void dfs(int t = 1, int i = 1, int s = 1, int e = N){
//printf("dfs(%d, %d, %d, %d)\n", t, i, s, e);
for(ii edge: edges[i]){
int u, v;
tie(u, v) = edge;
unionSet(u, v, t);
//assert(b[u] <= s && e <= a[u] && b[v] <= s && e <= a[v]);
//printf("Edge: %d %d %d\n", u, v, t);
}
if(s == e){
int c = s;
satisfied[c] = true;
for(int u: bList[c]){
//printf("c=%d u=%d\n", c, u);
bool boleh = false;
for(int v: aList[c]){
//printf("%d %d\n", u, v);
int x = findSet(u);
int y = findSet(v);
if(x == y){
boleh = true;
break;
}
}
if(!boleh){
satisfied[c] = false;
break;
}
}
//printf("satisfied[%d]=%d\n", c, (int)satisfied[c]);
return;
}else{
int l = (i<<1);
int r = (i<<1)|1;
int m = (s+e)>>1;
dfs(t+1, l, s, m);
dfs(t+1, r, m+1, e);
}
rollback(t);
}
int main(){
int t;
scanf("%d", &t);
while(t --){
scanf("%d%d", &N, &M);
for(int i = 1; i <= N; i ++){
aList[i].clear();
bList[i].clear();
}
for(int i = 1; i <= N; i ++){
scanf("%d", &a[i]);
aList[a[i]].push_back(i);
}
for(int i = 1; i <= N; i ++){
scanf("%d", &b[i]);
bList[b[i]].push_back(i);
}
for(int i = 0; i < M; i ++){
int u, v;
scanf("%d%d", &u, &v);
EdgeList[i] = ii(u, v);
}
int ans = 1;
for(int i = 1; i <= N; i ++){
if(a[i] < b[i]){
ans = 0;
break;
}
}
if(ans == 0){
printf("%d\n", ans);
continue;
}
P = 0;
for(int i = 0; i < M; i ++){
int u, v;
tie(u, v) = EdgeList[i];
int s = max(b[u], b[v]);
int e = min(a[u], a[v]);
if(s <= e){
EdgeList2[P ++] = make_pair(ii(u, v), ii(s, e));
}
}
init();
for(int i = 0; i < P; i ++){
addEdge(EdgeList2[i].first.first, EdgeList2[i].first.second,
EdgeList2[i].second.first, EdgeList2[i].second.second);
}
init1(N);
for(int i = 1; i <= N; i ++){
satisfied[i] = true;
}
dfs();
ans = 1;
for(int i = 1; i <= N; i ++){
if(!satisfied[i]){
ans = 0;
break;
}
}
printf("%d\n", ans);
}
return 0;
}
Compilation message
colors.cpp: In function 'int main()':
colors.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
156 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
colors.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
158 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
colors.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
166 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
colors.cpp:171:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
171 | scanf("%d", &b[i]);
| ~~~~~^~~~~~~~~~~~~
colors.cpp:177:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
177 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
120 ms |
19796 KB |
Output is correct |
| 2 |
Correct |
53 ms |
19712 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19968 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
115 ms |
19960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
130 ms |
19916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
130 ms |
19916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
120 ms |
19796 KB |
Output is correct |
| 2 |
Correct |
53 ms |
19712 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19968 KB |
Output is correct |
| 4 |
Incorrect |
130 ms |
19916 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
246 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
78 ms |
19868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
120 ms |
19796 KB |
Output is correct |
| 2 |
Correct |
53 ms |
19712 KB |
Output is correct |
| 3 |
Correct |
18 ms |
19968 KB |
Output is correct |
| 4 |
Correct |
115 ms |
19960 KB |
Output is correct |
| 5 |
Incorrect |
130 ms |
19916 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
