/* ok this problem is marvelous */
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;
int t,n,m,ans,par[150005],siz[150005],a[150005],b[150005];
vector<int>A[150005],B[150005];
vector<int>nod[150005];
vector<pair<int,int>>tree[4*150005];
vector<pair<pair<int,int>,int>>DSU;
bitset<150005>viz;
void update(int l,int r,int le,int ri,pair<int,int>pi,int nod){
if(l>ri || r<le) return;
else if(l>=le && r<=ri) tree[nod].push_back(pi);
else{
int mid=l+(r-l)/2;
update(l,mid,le,ri,pi,2*nod);
update(mid+1,r,le,ri,pi,2*nod+1);
}
}
int findpar(int x){
if(x!=par[x]){
DSU.push_back({{x,par[x]},0});
par[x]=findpar(par[x]);
}
return par[x];
}
void conect(int x,int y){
int x1=findpar(x);
int y1=findpar(y);
if(x1!=y1){
if(siz[x1]<siz[y1]) swap(x1,y1);
DSU.push_back({{y1,par[y1]},siz[y1]});
par[y1]=x1;
siz[x1]+=siz[y1];
}
}
void ers(int x){
while(DSU.size()>x){
auto it=DSU.back();
DSU.pop_back();
par[it.fr.fr]-=it.sc;
par[it.fr.fr]=par[it.fr.sc];
}
}
void solve(int l,int r,int nod){
int sz=DSU.size();
for(auto it:tree[nod]){
conect(it.fr,it.sc);
}
if(l==r){
for(auto it:A[l]){
viz[findpar(it)]=1;
}
for(auto it:B[l]){
if(viz[findpar(it)]==0) ans=0;
}
for(auto it:A[l]){
viz[findpar(it)]=0;
}
}
else{
int mid=l+(r-l)/2;
solve(l,mid,2*nod);
solve(mid+1,r,2*nod+1);
}
ers(sz);
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
srand(chrono::steady_clock::now().time_since_epoch().count());
// ifstream cin("input.in");
cin >> t;
while(t--){
ans=1;
cin >> n >> m;
for(int i=1;i<=n;i++) par[i]=i,siz[i]=1;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++){
A[a[i]].push_back(i);
}
for(int i=1;i<=n;i++) cin >> b[i];
for(int i=1;i<=n;i++){
B[b[i]].push_back(i);
}
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
nod[x].push_back(y);
nod[y].push_back(x);
if(max(b[x],b[y])<=min(a[x],a[y])) update(1,n,max(b[x],b[y]),min(a[x],a[y]),{x,y},1);
}
solve(1,n,1);
for(int i=1;i<=n;i++) A[i].clear(),B[i].clear();
DSU.clear();
for(int i=1;i<=4*n;i++) tree[i].clear();
for(int i=1;i<=n;i++) nod[i].clear();
cout << ans << '\n';
}
}
Compilation message
colors.cpp: In function 'void ers(long long int)':
colors.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(DSU.size()>x){
~~~~~~~~~~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
399 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
407 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
390 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
390 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
399 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
401 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
385 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
399 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
