#include <bits/stdc++.h>
using namespace std;
int viz[150005],b[150005],a[150005],ok[150005],t,n,m,i,x,y,j,ok1;
int sal[150005],fr[150005],tata[150005],rang[150005],stanga,dreapta;
struct wow
{
int x,y;
} muchii[200005];
vector <int> cinea[150005],cineb[150005];
vector <int> arb[800005];
int parinte (int x)
{
if (x!=tata[x])
{
return parinte(tata[x]);
}
return x;
}
int q;
struct cetin
{
int poz,rangpoz,tatapoz;
};
cetin baubau[800005];
void update(int st,int dr,int nod,int ua,int ub,int poz)
{
if (ua<=st&&dr<=ub)
{
arb[nod].push_back(poz);
return;
}
int mij=(st+dr)/2;
if (ua<=mij)
{
update(st,mij,2*nod,ua,ub,poz);
}
if (mij<ub)
{
update(mij+1,dr,2*nod+1,ua,ub,poz);
}
}
void uneste(int x,int y)
{
x=parinte(x);
y=parinte(y);
if (rang[x]<rang[y])
{
baubau[++q]=cetin{x,rang[x],tata[x]};
tata[x]=tata[y];
}
else if (rang[x]>rang[y])
{
baubau[++q]=cetin{y,rang[y],tata[y]};
tata[y]=tata[x];
}
else if (rang[x]==rang[y])
{
baubau[++q]=cetin{x,rang[x],tata[x]};
tata[x]=tata[y];
}
}
int numar=0;
void dfs(int st,int dr,int nod)
{
int salut2=0;
for (int i=0; i<arb[nod].size(); i++)
{
int x=muchii[arb[nod][i]].x;
int y=muchii[arb[nod][i]].y;
if (parinte(x)!=parinte(y))
{
salut2++;
uneste(x,y);
}
}
if (st==dr)
{
int i;
for (i=0; i<cinea[st].size(); i++)
{
fr[parinte(cinea[st][i])]++;
}
for (i=0; i<cineb[st].size(); i++)
{
if (fr[parinte(cineb[st][i])]!=0)
{
numar++;
}
}
for (i=0; i<cinea[st].size(); i++)
{
fr[parinte(cinea[st][i])]--;
}
return;
}
int mij=(st+dr)/2;
dfs(st,mij,2*nod);
dfs(mij+1,dr,2*nod+1);
for (int i=salut2; i>=1; i--)
{
int pozitie=baubau[q].poz;
tata[pozitie]=baubau[q].tatapoz;
rang[pozitie]=baubau[q].rangpoz;
q--;
}
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>t;
for (; t--;)
{
cin>>n>>m;
for (i=1; i<=n; i++)
{
cin>>a[i];
ok[i]=0;
}
for (i=1; i<=n; i++)
{
cin>>b[i];
}
ok1=1;
for (i=1; i<=n; i++)
{
tata[i]=i;
rang[i]=1;
fr[i]=0;
}
for (i=1; i<=n; i++)
{
cinea[i].clear();
cineb[i].clear();
}
for (i=1; i<=n; i++)
{
cinea[a[i]].push_back(i);
cineb[b[i]].push_back(i);
}
for (i=1; i<=4*n; i++)
{
arb[i].clear();
}
for (i=1; i<=m; i++)
{
cin>>muchii[i].x>>muchii[i].y;
}
for (i=1; i<=n; i++)
{
if (b[i]>a[i])
{
cout<<"0"<<'\n';
ok1=0;
break;
}
}
if (ok1==0)
{
continue;
}
for (i=1;i<=m;i++)
{
x=muchii[i].x;y=muchii[i].y;
stanga=max(b[x],b[y]);
dreapta=min(a[x],a[y]);
update(1,n,1,stanga,dreapta,i);
}
numar=0;
q=0;
dfs(1,n,1);
if (numar!=n)
{
cout<<"0"<<'\n';
}
else
{
cout<<"1"<<'\n';
}
}
return 0;
}
Compilation message
colors.cpp: In function 'void dfs(int, int, int)':
colors.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i=0; i<arb[nod].size(); i++)
| ~^~~~~~~~~~~~~~~~
colors.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (i=0; i<cinea[st].size(); i++)
| ~^~~~~~~~~~~~~~~~~
colors.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (i=0; i<cineb[st].size(); i++)
| ~^~~~~~~~~~~~~~~~~
colors.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (i=0; i<cinea[st].size(); i++)
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
26188 KB |
Output is correct |
| 2 |
Correct |
57 ms |
26220 KB |
Output is correct |
| 3 |
Correct |
59 ms |
26380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
26284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
26320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
26320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
26188 KB |
Output is correct |
| 2 |
Correct |
57 ms |
26220 KB |
Output is correct |
| 3 |
Correct |
59 ms |
26380 KB |
Output is correct |
| 4 |
Incorrect |
86 ms |
26320 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
177 ms |
26192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
26176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
26188 KB |
Output is correct |
| 2 |
Correct |
57 ms |
26220 KB |
Output is correct |
| 3 |
Correct |
59 ms |
26380 KB |
Output is correct |
| 4 |
Correct |
89 ms |
26284 KB |
Output is correct |
| 5 |
Incorrect |
86 ms |
26320 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
