# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
230639 |
2020-05-10T16:56:45 Z |
2fat2code |
Colors (RMI18_colors) |
C++17 |
|
155 ms |
27000 KB |
/* 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();
siz[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){
~~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
26616 KB |
Output is correct |
2 |
Correct |
45 ms |
25856 KB |
Output is correct |
3 |
Correct |
23 ms |
25856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
27000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
90 ms |
26616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
90 ms |
26616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
26616 KB |
Output is correct |
2 |
Correct |
45 ms |
25856 KB |
Output is correct |
3 |
Correct |
23 ms |
25856 KB |
Output is correct |
4 |
Incorrect |
90 ms |
26616 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
155 ms |
26840 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
56 ms |
26108 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
26616 KB |
Output is correct |
2 |
Correct |
45 ms |
25856 KB |
Output is correct |
3 |
Correct |
23 ms |
25856 KB |
Output is correct |
4 |
Correct |
86 ms |
27000 KB |
Output is correct |
5 |
Incorrect |
90 ms |
26616 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |