#include <bits/stdc++.h>
#define DIM 300010
#define INF 2000000000
using namespace std;
vector <int> L[DIM],poz[DIM*4],poz_a[DIM],poz_b[DIM];
int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM],v[DIM],viz[DIM],E[DIM*4],first[DIM],level[DIM],p[DIM*4],idx[DIM];
int mrk[DIM],fth[DIM],Size[DIM];
int t,n,m,i,j,x,y,k,sol,mini,maxi,ok,g,sol_final;
struct seg_tree{
int minia,maxib;
} aint[4*DIM];
struct idk{
int nod, minia, maxib;
} dp[DIM][30];
pair <int,int> rmq[30][DIM*4];
vector <pair<int,int> > aint2[DIM*4];
deque <pair<int,int> > s;
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].minia = a[v[st]];
aint[nod].maxib = b[v[st]];
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
aint[nod].minia = min (aint[nod<<1].minia,aint[(nod<<1)|1].minia);
aint[nod].maxib = max (aint[nod<<1].maxib,aint[(nod<<1)|1].maxib);
}
void query (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y){
mini = min (mini,aint[nod].minia);
maxi = max (maxi,aint[nod].maxib);
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 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 (a[v[i]] == b[v[i]])
continue;
int lft = 0, rgh = 0;
for (auto it : poz[b[v[i]]]){
if (it < i)
lft = it;
if (it > i){
rgh = it;
break;
}
}
int ok2 = 0;
if (lft){
mini = INF, maxi = -INF;
query (1,1,k,lft,i-1);
if (mini >= b[v[i]] && maxi <= b[v[i]])
ok2 = 1;
}
if (rgh){
mini = INF, maxi = -INF;
query (1,1,k,i+1,rgh);
if (mini >= b[v[i]] && maxi <= b[v[i]])
ok2 = 1;
}
if (!ok2){
ok = 0;
break;
}}
return ok;
}
void dfs2 (int nod){
viz[nod] = 1;
if (nod != i && a[nod] == b[i])
g = 1;
for (auto vecin : L[nod])
if (!viz[vecin])
if (a[vecin] >= b[i] && b[vecin] <= b[i])
dfs2 (vecin);
}
void dfs3 (int nod, int tata){
dp[nod][0] = {tata, a[nod],b[nod]};
E[++k] = nod;
first[nod] = k;
level[nod] = 1 + level[tata];
for (auto vecin : L[nod])
if (vecin != tata){
dfs3 (vecin,nod);
E[++k] = nod;
}
}
int get_lca (int x, int y){
int posx = first[x], posy = first[y];
if (posx > posy)
swap (posx,posy);
int nr = p[posy - posx + 1];
pair <int, int> sol = min (rmq[nr][posx], rmq[nr][posy - (1<<nr) + 1]);
return E[sol.second];
}
void solve2 (int x, int y){
int lca = get_lca (x,y);
for (int i=20;i>=0;i--){
if (dp[x][i].nod && level[dp[x][i].nod] >= level[lca]){
mini = min (mini,dp[x][i].minia);
maxi = max (maxi,dp[x][i].maxib);
x = dp[x][i].nod;
}}
for (int i=20;i>=0;i--){
if (dp[y][i].nod && level[dp[y][i].nod] >= level[lca]){
mini = min (mini,dp[y][i].minia);
maxi = max (maxi,dp[y][i].maxib);
x = dp[y][i].nod;
}}}
void update_aint (int nod, int st, int dr, int x, int y, int a, int b){
if (x <= st && dr <= y){
aint2[nod].push_back(make_pair(a,b));
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update_aint(nod<<1,st,mid,x,y,a,b);
if (y > mid)
update_aint ((nod<<1)|1,mid+1,dr,x,y,a,b);
}
int get_rad (int x){
while (x != fth[x])
x = fth[x];
return x;
}
void unite (int radx, int rady){
if (radx == rady)
return;
if (Size[radx] > Size[rady]);
swap (radx,rady);
/// tin minte o stiva cu update urile pe care le fac ca sa pot sa fac undo
s.push_back(make_pair(radx,rady));
Size[radx] += Size[rady];
fth[rady] = radx;
}
void undo (){
int x = s.back().first, y = s.back().second;
s.pop_back();
Size[x] -= Size[y];
fth[y] = x;
}
void query_aint (int nod, int st, int dr){
/// am intrat prima oara in nod, trb sa adaug muchiile
int size_init = s.size(); /// ca sa stiu dupa cate undo uri trb sa fac
for (auto it : aint2[nod]){
int x = it.first, y = it.second;
int radx = get_rad (x), rady = get_rad (y);
unite (radx,rady);
}
if (st == dr){ /// acum trb sa fac query ul
/// marchez culorile de a
for (auto it : poz_a[st])
mrk[get_rad(it)] = st;
for (auto it : poz_b[st])
if (mrk[get_rad(it)] != st)
sol_final = 0;
return;
}
int mid = (st+dr)>>1;
query_aint(nod<<1,st,mid);
query_aint((nod<<1)|1,mid+1,dr);
/// am terminat cu nod, trb sa dau undo
int size_fin = s.size();
for (int i=1;i<=size_fin-size_init;i++)
undo();
}
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();
poz_a[i].clear();
poz_b[i].clear();
f[i] = 0;
}
for (i=1;i<=4*n;i++)
aint2[i].clear();
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);
/// fac update in aint cu intervalul pt muchia asta
update_aint (1,1,n,max(b[x],b[y]),min(a[x],a[y]),x,y);
}
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;
cnt = 0;
for (i=1;i<=n;i++)
if (L[i].size() == 1){
if (!start)
start = i;
cnt++;
}
if (cnt == 2 && m == n-1){
memset (viz,0,sizeof viz); k = 0;
dfs (start);
if (solve (v,k))
cout<<"1\n";
else cout<<"0\n";
continue;
}
/// arbore
if (1LL*n*n <= 5000000){
for (i=1;i<=n;i++){
if (a[i] == b[i])
continue;
for (j=1;j<=n;j++)
viz[j] = 0;
g = 0;
dfs2 (i);
if (!g)
break;
}
if (i > n)
cout<<"1\n";
else cout<<"0\n";
continue;
}
/// permutarea
if (m == n-1){
k = 0;
dfs3 (1,0);
for (i=1;i<=k;i++)
rmq[0][i] = make_pair(level[E[i]],i);
for (i=1;(1<<i)<=k;i++)
for (j=1;j<=k;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
}
for (i=2;i<=k;i++)
p[i] = p[i/2] + 1;
for (j=1;(1<<j)<=n;j++)
for (i=1;i<=n;i++){
dp[i][j].nod = dp[dp[i][j-1].nod][j-1].nod;
dp[i][j].minia = min (dp[i][j-1].minia, dp[ dp[i][j-1].nod ][j-1].minia);
dp[i][j].maxib = max (dp[i][j-1].maxib, dp[ dp[i][j-1].nod ][j-1].maxib);
}
for (i=1;i<=n;i++)
idx[a[i]] = i;
for (i=1;i<=n;i++){
if (a[i] == b[i])
continue;
mini = INF, maxi = -INF;
solve2 (idx[b[i]],i);
if (mini < b[i] || maxi > b[i])
break;
}
if (i > n)
cout<<"1\n";
else cout<<"0\n";
continue;
}
/// de aici devine interesant
for (i=1;i<=n;i++){
poz_a[a[i]].push_back(i);
poz_b[b[i]].push_back(i);
fth[i] = i;
}
memset (Size,1,sizeof Size);
sol_final = 1;
query_aint (1,1,n);
cout<<sol_final<<"\n";
}
return 0;
}
Compilation message
colors.cpp: In function 'void unite(int, int)':
colors.cpp:170:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (Size[radx] > Size[rady]);
^~
colors.cpp:171:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
swap (radx,rady);
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
79352 KB |
Output is correct |
| 2 |
Correct |
107 ms |
78584 KB |
Output is correct |
| 3 |
Correct |
50 ms |
78200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
79736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
420 ms |
80760 KB |
Output is correct |
| 2 |
Correct |
124 ms |
79480 KB |
Output is correct |
| 3 |
Correct |
54 ms |
79360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
420 ms |
80760 KB |
Output is correct |
| 2 |
Correct |
124 ms |
79480 KB |
Output is correct |
| 3 |
Correct |
54 ms |
79360 KB |
Output is correct |
| 4 |
Correct |
655 ms |
82220 KB |
Output is correct |
| 5 |
Correct |
828 ms |
103732 KB |
Output is correct |
| 6 |
Correct |
1184 ms |
132492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
79352 KB |
Output is correct |
| 2 |
Correct |
107 ms |
78584 KB |
Output is correct |
| 3 |
Correct |
50 ms |
78200 KB |
Output is correct |
| 4 |
Correct |
420 ms |
80760 KB |
Output is correct |
| 5 |
Correct |
124 ms |
79480 KB |
Output is correct |
| 6 |
Correct |
54 ms |
79360 KB |
Output is correct |
| 7 |
Correct |
253 ms |
80632 KB |
Output is correct |
| 8 |
Correct |
135 ms |
79864 KB |
Output is correct |
| 9 |
Correct |
98 ms |
78200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
485 ms |
82252 KB |
Output is correct |
| 2 |
Correct |
924 ms |
130680 KB |
Output is correct |
| 3 |
Correct |
1055 ms |
206568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
79992 KB |
Output is correct |
| 2 |
Correct |
88 ms |
78584 KB |
Output is correct |
| 3 |
Correct |
97 ms |
78200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
79352 KB |
Output is correct |
| 2 |
Correct |
107 ms |
78584 KB |
Output is correct |
| 3 |
Correct |
50 ms |
78200 KB |
Output is correct |
| 4 |
Correct |
223 ms |
79736 KB |
Output is correct |
| 5 |
Correct |
420 ms |
80760 KB |
Output is correct |
| 6 |
Correct |
124 ms |
79480 KB |
Output is correct |
| 7 |
Correct |
54 ms |
79360 KB |
Output is correct |
| 8 |
Correct |
655 ms |
82220 KB |
Output is correct |
| 9 |
Correct |
828 ms |
103732 KB |
Output is correct |
| 10 |
Correct |
1184 ms |
132492 KB |
Output is correct |
| 11 |
Correct |
253 ms |
80632 KB |
Output is correct |
| 12 |
Correct |
135 ms |
79864 KB |
Output is correct |
| 13 |
Correct |
98 ms |
78200 KB |
Output is correct |
| 14 |
Correct |
485 ms |
82252 KB |
Output is correct |
| 15 |
Correct |
924 ms |
130680 KB |
Output is correct |
| 16 |
Correct |
1055 ms |
206568 KB |
Output is correct |
| 17 |
Correct |
149 ms |
79992 KB |
Output is correct |
| 18 |
Correct |
88 ms |
78584 KB |
Output is correct |
| 19 |
Correct |
97 ms |
78200 KB |
Output is correct |
| 20 |
Correct |
359 ms |
80632 KB |
Output is correct |
| 21 |
Execution timed out |
3080 ms |
84896 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
