#include <bits/stdc++.h>
#define DIM 150010
#define DIMBUFF 7000000
#define INF 2000000000
using namespace std;
vector <int> poz_a[DIM],poz_b[DIM];
int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM];
int mrk[DIM],fth[DIM],Size[DIM];
int t,n,m,i,j,x,y,k,sol,mini,maxi,ok,g,sol_final,u,pos;
char buff[DIMBUFF];
vector <pair<int,int> > aint2[DIM*4];
pair<int,int> s[DIM];
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[++u] = make_pair(radx,rady);
Size[radx] += Size[rady];
fth[rady] = radx;
}
void undo (){
int x = s[u].first, y = s[u].second;
u--;
Size[x] -= Size[y];
fth[y] = y;
}
void query_aint (int nod, int st, int dr){
/// am intrat prima oara in nod, trb sa adaug muchiile
if (!sol_final)
return;
int size_init = u; /// ca sa stiu dupa cate undo uri trb sa fac
for (auto it : aint2[nod]){
int radx = get_rad (it.first), rady = get_rad (it.second);
unite (radx,rady);
}
if (st == dr){ /// acum trb sa fac query ul
/// marchez culorile de a
for (int i=0;i<poz_a[st].size();++i){
int x = poz_a[st][i];
mrk[get_rad(x)] = st;
}
for (int i=0;i<poz_b[st].size();++i){
int x = poz_b[st][i];
if (mrk[get_rad(x)] != st){
sol_final = 0;
break;
}
}
} else {
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
while (u > size_init)
undo();
}
int get_nr(){
while (!(buff[pos] >= '0' && buff[pos] <= '9'))
pos++;
int nr = 0;
while (buff[pos] >= '0' && buff[pos] <= '9'){
nr = nr*10 + buff[pos] - '0';
pos++;
}
return nr;
}
int main (){
//FILE *fin = fopen ("colors2.in","r");
//FILE *fout = fopen ("colors2.out","w");
FILE *fin = stdin;
FILE *fout = stdout;
fread (buff,1,DIMBUFF,fin);
t = get_nr();
for (int q=1;q<=t;++q){
//if (q == 36)
// q = 36;
//cin>>n>>m;
n = get_nr(), m = get_nr();
for (i=1;i<=n;++i){
//L[i].clear();
poz_a[i].clear();
poz_b[i].clear();
f[i] = mrk[i] = 0;
Size[i] = 1;
fth[i] = i;
}
for (i=1;i<=4*n;++i)
aint2[i].clear();
for (i=1;i<=n;++i){
//cin>>a[i];
a[i] = get_nr();
++f[a[i]];
poz_a[a[i]].push_back(i);
}
int ok = 1;
for (i=1;i<=n;++i){
//cin>>b[i];
b[i] = get_nr();
poz_b[b[i]].push_back(i);
if (b[i] > a[i] || !f[b[i]])
ok = 0;
}
for (i=1;i<=m;++i){
//cin>>x>>y;
x = get_nr(), y = get_nr();
/// 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";
fprintf(fout,"0\n");
continue;
}
if (n == 1 && !m){
if (a[1] == b[1])
fprintf(fout,"1\n");
else fprintf(fout,"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]) )
fprintf(fout,"1\n");
else fprintf(fout,"0\n");
continue;
}
/// de aici devine interesant
sol_final = 1;
//s.clear();
u = 0;
query_aint (1,1,n);
fprintf(fout,"%d\n",sol_final);
//cout<<sol_final<<"\n";
}
return 0;
}
Compilation message
colors.cpp: In function 'void unite(int, int)':
colors.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (Size[radx] < Size[rady]);
^~
colors.cpp:39:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
swap (radx,rady);
^~~~
colors.cpp: In function 'void query_aint(int, int, int)':
colors.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<poz_a[st].size();++i){
~^~~~~~~~~~~~~~~~~
colors.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<poz_b[st].size();++i){
~^~~~~~~~~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:111:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread (buff,1,DIMBUFF,fin);
~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
23032 KB |
Output is correct |
| 2 |
Correct |
35 ms |
22144 KB |
Output is correct |
| 3 |
Correct |
32 ms |
21888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
23416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
23040 KB |
Output is correct |
| 2 |
Correct |
26 ms |
22144 KB |
Output is correct |
| 3 |
Correct |
18 ms |
21888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
23040 KB |
Output is correct |
| 2 |
Correct |
26 ms |
22144 KB |
Output is correct |
| 3 |
Correct |
18 ms |
21888 KB |
Output is correct |
| 4 |
Correct |
81 ms |
24832 KB |
Output is correct |
| 5 |
Correct |
300 ms |
43728 KB |
Output is correct |
| 6 |
Runtime error |
653 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
23032 KB |
Output is correct |
| 2 |
Correct |
35 ms |
22144 KB |
Output is correct |
| 3 |
Correct |
32 ms |
21888 KB |
Output is correct |
| 4 |
Correct |
46 ms |
23040 KB |
Output is correct |
| 5 |
Correct |
26 ms |
22144 KB |
Output is correct |
| 6 |
Correct |
18 ms |
21888 KB |
Output is correct |
| 7 |
Correct |
49 ms |
24576 KB |
Output is correct |
| 8 |
Correct |
30 ms |
22656 KB |
Output is correct |
| 9 |
Correct |
22 ms |
21888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
27776 KB |
Output is correct |
| 2 |
Correct |
1038 ms |
49136 KB |
Output is correct |
| 3 |
Runtime error |
2164 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
23168 KB |
Output is correct |
| 2 |
Correct |
27 ms |
22528 KB |
Output is correct |
| 3 |
Correct |
26 ms |
21888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
23032 KB |
Output is correct |
| 2 |
Correct |
35 ms |
22144 KB |
Output is correct |
| 3 |
Correct |
32 ms |
21888 KB |
Output is correct |
| 4 |
Correct |
57 ms |
23416 KB |
Output is correct |
| 5 |
Correct |
46 ms |
23040 KB |
Output is correct |
| 6 |
Correct |
26 ms |
22144 KB |
Output is correct |
| 7 |
Correct |
18 ms |
21888 KB |
Output is correct |
| 8 |
Correct |
81 ms |
24832 KB |
Output is correct |
| 9 |
Correct |
300 ms |
43728 KB |
Output is correct |
| 10 |
Runtime error |
653 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
