#include <bits/stdc++.h>
#define DIM 150010
#define INF 2000000000
using namespace std;
vector <int> L[DIM],poz[DIM*4];
int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM],v[DIM],viz[DIM];
int t,n,m,i,j,x,y,k,sol;
struct seg_tree{
int mini,lazy;
} aint[4*DIM];
void dfs (int nod){
viz[nod] = 1;
v[++k] = nod;
for (auto vecin : L[nod])
if (!viz[vecin])
dfs (vecin);
}
void build (int nod, int st, int dr){
if (st == dr){
aint[nod].mini = a[v[st]];
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
aint[nod].mini = min (aint[nod<<1].mini,aint[(nod<<1)|1].mini);
}
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
aint[nod<<1].mini = aint[nod<<1].lazy = aint[nod].lazy;
aint[(nod<<1)|1].mini = aint[(nod<<1)|1].lazy = aint[nod].lazy;
}
aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
aint[nod].mini = val;
aint[nod].lazy = val;
update_lazy (nod,st,dr);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
aint[nod].mini = min (aint[nod<<1].mini,aint[(nod<<1)|1].mini);
}
void query (int nod, int st, int dr, int x, int y){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
sol = min (sol,aint[nod].mini);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query(nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
int get_elem (int nod, int st, int dr, int poz){
update_lazy (nod,st,dr);
if (st == dr)
return aint[nod].mini;
int mid = (st+dr)>>1;
if (poz <= mid)
return get_elem (nod<<1,st,mid,poz);
else return get_elem ((nod<<1)|1,mid+1,dr,poz);
}
int solve (int v[], int k){
for (i=1;i<=4*k;i++){
poz[i].clear();
aint[i] = {0,0};
}
for (i=1;i<=k;i++)
poz[a[v[i]]].push_back(i);
build (1,1,k);
int ok = 1;
for (i=1;i<=k;i++){
if (get_elem (1,1,k,i) == b[v[i]])
continue;
/// caut b[v[i]];
int x = v[i], p = 0;
if (i > 1 && get_elem (1,1,k,i-1) == b[x]){
update (1,1,k,i,i,b[x]);
continue;
}
for (auto it : poz[b[x]]){
if (it <= i)
continue;
if (get_elem (1,1,k,it) == b[x]){
p = it;
break;
}}
if (!p){
ok = 0;
break;
}
/// minimul din interval
sol = INF;
query (1,1,k,i,p);
if (sol < b[x]){
ok = 0;
break;
}
update (1,1,k,i,p,b[x]);
}
return ok;
}
int main (){
/// ifstream cin ("colors2.in");
/// ofstream cout ("colors2.out");
cin>>t;
for (int q=1;q<=t;q++){
if (q == 36)
q = 36;
cin>>n>>m;
for (i=1;i<=n;i++){
L[i].clear();
f[i] = 0;
}
for (i=1;i<=n;i++){
cin>>a[i];
f[a[i]]++;
}
int ok = 1;
for (i=1;i<=n;i++){
cin>>b[i];
if (b[i] > a[i] || !f[b[i]])
ok = 0;
}
for (i=1;i<=m;i++){
cin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
if (!ok){
cout<<0<<"\n";
continue;
}
if (n == 1 && !m){
if (a[1] == b[1])
cout<<"1\n";
else cout<<"0\n";
continue;
}
if (n == 2 && m == 1){
if ( (a[1] == b[1] && a[2] == b[2]) || (min (a[1],a[2]) == b[1] && min (a[1],a[2]) == b[2]) )
cout<<"1\n";
else cout<<"0\n";
continue;
}
/// graf stea
int nod = 0, cnt = 0;
for (i=1;i<=n;i++){
if (L[i].size() == 1)
cnt++;
else nod = i;
}
if (cnt == n-1){
int maxi = 0, mini = n+1;
for (i=1;i<=n;i++){
if (b[i] == a[i])
continue;
maxi = max (maxi,b[i]);
if (i != nod)
mini = min (mini,b[i]);
}
if (maxi && (maxi > a[nod] || mini < b[nod])){
cout<<"0\n";
continue;
}
/// acum sa vad daca exista b[nod]
int ok = 0;
if (!maxi)
ok = 1;
for (i=1;i<=n;i++)
if (i != nod && b[i] == b[nod]){
ok = 1;
break;
}
cout<<ok<<"\n";
continue;
}
/// graf complet
if (m == 1LL*n*(n-1)/2){
cout<<1<<"\n";
continue;
}
/// lant
int start = 0;
for (i=1;i<=n;i++)
if (L[i].size() == 1){
start = i;
break;
}
memset (viz,0,sizeof viz); k = 0;
dfs (start);
if (solve (v,k))
cout<<"1\n";
else {
reverse (v+1,v+k+1);
if (solve (v,k))
cout<<"1\n";
else cout<<"0\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
19448 KB |
Output is correct |
| 2 |
Correct |
68 ms |
18528 KB |
Output is correct |
| 3 |
Correct |
26 ms |
18048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
19680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
20016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
20016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
19448 KB |
Output is correct |
| 2 |
Correct |
68 ms |
18528 KB |
Output is correct |
| 3 |
Correct |
26 ms |
18048 KB |
Output is correct |
| 4 |
Incorrect |
306 ms |
20016 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
525 ms |
21716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
19320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
19448 KB |
Output is correct |
| 2 |
Correct |
68 ms |
18528 KB |
Output is correct |
| 3 |
Correct |
26 ms |
18048 KB |
Output is correct |
| 4 |
Correct |
188 ms |
19680 KB |
Output is correct |
| 5 |
Incorrect |
306 ms |
20016 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
