| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 306974 |
2020-09-26T15:40:21 Z |
bigDuck |
Colors (RMI18_colors) |
C++14 |
|
353 ms |
11776 KB |
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll
int t, n, m, a[150010], b[150010];
vector<int> oa[150010], ob[150010];
vector<int> g[150010];
struct query{
int type, u, v, l, r;
};
vector<query> q;
struct DSU{
int ptr[150010], sz[150010];bool mrk[150010];
};
DSU dsu;
void build(){for(int i=1; i<=n; i++){dsu.ptr[i]=i; dsu.sz[i]=1; dsu.mrk[i]=false;}return;}
struct ch{
int u, v, t;
};
stack<ch> st;
int find_root(int x){int cr=x; while(cr!=dsu.ptr[cr]){cr=dsu.ptr[cr];} return cr;}
void unite(int u, int v, int t){
int ru=find_root(u), rv=find_root(v);
if(ru==rv){return;}
if(dsu.sz[ru]>=dsu.sz[rv]){
dsu.ptr[rv]=ru; dsu.sz[ru]+=dsu.sz[rv];
ch c; c.u=ru; c.v=rv; c.t=t; st.push(c);
}
else{
dsu.ptr[ru]=rv; dsu.sz[rv]+=dsu.sz[ru];
ch c; c.u=rv; c.v=ru; c.t=t; st.push(c);
}
return;
}
void separate(int u, int v){
if(u==v){return;}
dsu.ptr[v]=v; dsu.sz[u]-=dsu.sz[v];
return;
}
void roll_back(int t){
while((st.size()>0) && (st.top().t>=t) ){
auto c=st.top(); separate(c.u, c.v); st.pop();
}
return;
}
bool rec(int l, int r, int t){
bool res=true;
if(l==r){
for(auto u:oa[l]){
int rt=find_root(u);
dsu.mrk[rt]=true;
}
for(auto u:ob[l]){
int rt=find_root(u);
if(dsu.mrk[rt]==false){
res=false; break;
}
}
for(auto u:oa[l]){
int rt=find_root(u);
dsu.mrk[rt]=false;
}
return res;
}
int med=(l+r)/2;
for(auto q0:q){
if( (q0.type==2) && (q0.l<=l) && (q0.r>=med) ){
unite(q0.u, q0.v, t);
}
}
res=rec(l, med, t+1);
roll_back(t);
if(res==false){return false;}
for(auto q0:q){
if( (q0.type==2) && (q0.l<=(med+1)) && (q0.r>=r) ){
unite(q0.u, q0.v, t);
}
}
res=rec(med+1, r, t+1);
roll_back(t);
return res;
}
map<pii, int> h_lt; set<pii> s;
void add_edges(int u, int t, int tp){
for(auto v:g[u]){
if(tp==2){
if( (a[v]>=a[u]) && (b[v]<=a[u]) ){
int i=u, j=v; if(i>j){swap(i, j);}
if(s.find(mp(i, j))==s.end()){
s.insert(mp(i, j));
h_lt[mp(i, j)]=t;
}
}
}
else{
if( ((a[v]>=b[u]) && (b[v]<=b[u])) && (a[v]>=t) ){
int i=u, j=v; if(i>j){swap(i, j);}
if(s.find(mp(i, j))==s.end()){
s.insert(mp(i, j));
h_lt[mp(i, j)]=t;
}
}
}
}
}
void remove_edges(int u, int t){
for(auto v:g[u]){
int i=u, j=v; if(i>j){swap(i, j);}
if(s.find(mp(i, j))!=s.end() ){
s.erase(mp(i, j));
query q0; q0.type=2; q0.u=i; q0.v=j; q0.l=h_lt[mp(i, j)]; q0.r=t;
q.pb(q0);
}
}
return;
}
void build_queries(){
for(int i=1; i<=(n+1); i++){
for(auto u:oa[i-1]){
remove_edges(u, i-1);
}
for(auto u:oa[i]){
add_edges(u, i, 2);
}
for(auto u:ob[i]){
add_edges(u, i, 1);
}
}
}
int32_t main(){
INIT
cin>>t;
while(t--){
q.clear(); h_lt.clear(); s.clear();
build();
cin>>n>>m;
for(int i=1; i<=n; i++){cin>>a[i];oa[a[i] ].pb(i); }
for(int i=1; i<=n; i++){cin>>b[i]; ob[b[i] ].pb(i); }
for(int i=1; i<=m; i++){
int u, v; cin>>u>>v;
g[u].pb(v); g[v].pb(u);
}
build_queries();
bool res=rec(1, n, 1);
for(int i=1; i<=n; i++){
if(b[i]>a[i]){res=false; break;}
}
cout<<res<<"\n";
for(int i=1; i<=n; i++){g[i].clear();oa[i].clear();ob[i].clear();}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
11000 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
11260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
278 ms |
11176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
11000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
11000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
11000 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
11260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
353 ms |
11128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
11128 KB |
Output is correct |
| 2 |
Correct |
69 ms |
11776 KB |
Output is correct |
| 3 |
Correct |
59 ms |
11392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
11000 KB |
Output is correct |
| 2 |
Incorrect |
77 ms |
11260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
