| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 403231 |
2021-05-12T23:58:28 Z |
jamezzz |
Colors (RMI18_colors) |
C++14 |
|
255 ms |
56596 KB |
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;
typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
int n,m,a[150005],b[150005],u[150005],v[150005];
bool ans[150005];
vector<int> qry[150005],have[150005];
struct union_find{
int par[150005],sz[150005];
stack<ii> st;
int fp(int i){
return (par[i]==i)?i:fp(par[i]);
}
void join(int x,int y){
x=fp(x),y=fp(y);
if(sz[x]<sz[y])swap(x,y);
par[y]=x;sz[x]+=sz[y];
st.push(ii(x,y));
}
void rollback(int left){
while(left<st.size()){
int x,y;tie(x,y)=st.top();st.pop();
par[y]=y;sz[x]-=sz[y];
}
}
}ufds;
struct node{
int s,e,m;vii v;
node *l,*r;
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 add(int x,int y,ii nv){
if(s==x&&e==y){
v.pb(nv);return;
}
if(y<=m)l->add(x,y,nv);
else if(x>m)r->add(x,y,nv);
else l->add(x,m,nv),r->add(m+1,y,nv);
}
void descend(){
int enter_size=ufds.st.size();
for(ii p:v){
debug("join: %d %d\n",p.fi,p.se);
ufds.join(p.fi,p.se);
}
if(s==e){
set<int> src;
for(int x:have[s])src.insert(ufds.fp(x));
for(int x:qry[s]){
int par=ufds.fp(x);
if(src.find(par)!=src.end())ans[x]=true;
else ans[x]=false;
}
}
else{
l->descend();
r->descend();
}
ufds.rollback(enter_size);
}
}*root;
int main(){
int t;sf("%d",&t);
while(t--){
sf("%d%d",&n,&m);
bool pos=true;
root=new node(1,n);
for(int i=1;i<=n;++i)sf("%d",&a[i]);
for(int i=1;i<=n;++i)sf("%d",&b[i]);
for(int i=0;i<m;++i)sf("%d%d",&u[i],&v[i]);
for(int i=1;i<=n;++i){
if(b[i]>a[i]){
pos=false;
}
ufds.sz[i]=1;
ufds.par[i]=i;
qry[b[i]].pb(i);
have[a[i]].pb(i);
}
if(!pos){
printf("0\n");
continue;
}
for(int i=0;i<m;++i){
int lo=max(b[u[i]],b[v[i]]);
int hi=min(a[u[i]],a[v[i]]);
debug("edge: %d %d %d %d\n",u[i],v[i],lo,hi);
if(lo>hi)continue;
root->add(lo,hi,ii(u[i],v[i]));
}
root->descend();
for(int i=1;i<=n;++i)pos=pos&&ans[i];
pf("%d\n",pos);
for(int i=1;i<=n;++i)qry[i].clear(),have[i].clear();
}
}
/*
2
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2
*/
Compilation message
colors.cpp: In member function 'void union_find::rollback(int)':
colors.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | while(left<st.size()){
| ~~~~^~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | int t;sf("%d",&t);
| ^
colors.cpp:110:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | sf("%d%d",&n,&m);
| ^
colors.cpp:113:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | for(int i=1;i<=n;++i)sf("%d",&a[i]);
| ^
colors.cpp:114:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | for(int i=1;i<=n;++i)sf("%d",&b[i]);
| ^
colors.cpp:115:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | for(int i=0;i<m;++i)sf("%d%d",&u[i],&v[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
30688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
16780 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
31276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
31276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
30688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
56596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
12612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
30688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
