| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 477910 |
2021-10-04T15:17:21 Z |
stefantaga |
Colors (RMI18_colors) |
C++14 |
|
254 ms |
524292 KB |
#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++)
{
if (b[i]>a[i])
{
cout<<"0"<<'\n';
ok1=0;
break;
}
}
if (ok1==0)
{
continue;
}
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<=m;i++)
{
cin>>x>>y;
muchii[i].x=x;muchii[i].y=y;
stanga=max(b[x],b[y]);
dreapta=min(a[x],a[y]);
update(1,m,1,stanga,dreapta,i);
}
numar=0;
dfs(1,m,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:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i=0;i<arb[nod].size();i++)
| ~^~~~~~~~~~~~~~~~
colors.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (i=0;i<cinea[st].size();i++)
| ~^~~~~~~~~~~~~~~~~
colors.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (i=0;i<cineb[st].size();i++)
| ~^~~~~~~~~~~~~~~~~
colors.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (i=0;i<cinea[st].size();i++)
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
52864 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
245 ms |
524292 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
52936 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
52936 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
52864 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
148 ms |
53228 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
254 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
52864 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
