# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
261045 |
2020-08-11T10:30:26 Z |
dvdg6566 |
Colors (RMI18_colors) |
C++14 |
|
385 ms |
29432 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MOD = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 160000;
const ll BSIZ= 800;
struct DSU{
int p[MAXN];
int sz[MAXN];
stack<pi> stk;
int N;
int par(int x){return (p[x]==x)?x:par(p[x]);}
DSU(){
for(int i=1;i<MAXN;++i){
p[i]=i;
sz[i]=1;
}
}
void merge(int a,int b){
// cerr<<"Merge "<<a<<' '<<b<<'\n';
a=par(a);b=par(b);
if(a==b){
stk.push(mp(-1,-1));
return;
}
// if(sz[a]<sz[b])swap(a,b);
p[b]=a;
sz[a]=sz[a]+sz[b];
stk.push(mp(b, sz[b]));// merging b into a
}
void reverse(){
// cerr<<"Split "<<edges.back().f<<' '<<edges.back().s<<'\n';
pi x=stk.top();stk.pop();
if(x.f==-1)return;
int b=x.f;
int a=p[b];
int bsiz=x.s;
p[b]=b;
sz[a]-=bsiz;
int k=0;
for(int i=1;i<=N;++i)if(par(i)==i)k+=sz[i];
assert(k==N);
}
}*ufds;
int T,N,E,a,b;
int A[MAXN];
int B[MAXN];
int ans;
vi starts[MAXN];
vi ee[MAXN];
int easy[MAXN];
struct node{
int s,e,m;
node *l,*r;
vpi V;
node(int _s,int _e):s(_s),e(_e){
m=(s+e)/2;
if(s!=e){l=new node(s,m);r=new node(m+1,e);}
}
void addedge(int x,int y,pi z){
if(s==x&&e==y){
V.pb(z);return;
}
if(y<=m)l->addedge(x,y,z);
else if(x>m)r->addedge(x,y,z);
else{
l->addedge(x,m,z);
r->addedge(m+1,y,z);
}
}
void solve(int N){
for(auto i:V){
ufds->merge(i.f,i.s);
}
if(s!=e){
l->solve(N);
if(m<N)r->solve(N);
}else{
if(SZ(ee[s])){
// cerr<<"Time "<<s<<'\n';
// for(auto i:starts[s])cerr<<ufds->par(i)<<' ';cerr<<'\n';
// for(auto i:ee[s])cerr<<ufds->par(i)<<' ';cerr<<'\n';
// ufds->db();
for(auto i:starts[s])easy[ufds->par(i)]=1;
for(auto i:ee[s])if(!easy[ufds->par(i)])ans=0;
for(auto i:starts[s])easy[ufds->par(i)]=0;
// cerr<<"Ans "<<ans<<'\n';
}
}
for(auto i:V)ufds->reverse();
V.clear();
}
}*root;
int main(){
cin>>T;
ufds=new DSU();
root=new node(1,MAXN);
while(T--){
cin>>N>>E;
ans=1;
for(int i=1;i<=N;++i){starts[i].clear();ee[i].clear();}
for(int i=1;i<=N;++i)cin>>A[i];
for(int i=1;i<=N;++i){
cin>>B[i];
ee[B[i]].pb(i);
starts[A[i]].pb(i);
if(B[i]>A[i])ans=0;
}
if(!ans){cout<<"0\n";continue;}
while(E--){
cin>>a>>b;
int latestart=max(B[a],B[b]);
int firstend=min(A[a],A[b]);
// cerr<<"Edge "<<a<<' '<<b<<" from "<<latestart<<' '<<firstend<<'\n';
if(latestart>firstend)continue;
root->addedge(latestart,firstend,mp(a,b));
}
root->solve(N);
cout<<ans<<'\n';
}
}
Compilation message
colors.cpp: In member function 'void node::solve(int)':
colors.cpp:106:12: warning: variable 'i' set but not used [-Wunused-but-set-variable]
for(auto i:V)ufds->reverse();
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
226 ms |
29184 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
82 ms |
29432 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
201 ms |
29180 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
201 ms |
29180 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
226 ms |
29184 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
385 ms |
29308 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
72 ms |
29304 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
226 ms |
29184 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |