oj.uz

Submission #306988

# Submission time Handle Problem Language Result Execution time Memory
306988 2020-09-26T16:26:02 Z bigDuck Colors (RMI18_colors) C++14
17 / 100
 237 ms 11188 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 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.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.l<=(med+1)) && (q0.r>=r) ){
        unite(q0.u, q0.v, t);
    }
}
res=rec(med+1, r, t+1);
roll_back(t);
return res;
}





int32_t main(){
INIT
cin>>t;

while(t--){
    q.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);
        query q0;
        q0.l=max(b[u], b[v]); q0.r=min(a[u], a[v]); q0.u=u; q0.v=v;
        if(q0.l<=q0.r){
        q.pb(q0);}
    }
    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;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 11000 KB Output is correct
2 Incorrect 58 ms 11008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 11008 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 11120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 11120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 11000 KB Output is correct
2 Incorrect 58 ms 11008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 11008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 11008 KB Output is correct
2 Correct 63 ms 11188 KB Output is correct
3 Correct 64 ms 11128 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 11000 KB Output is correct
2 Incorrect 58 ms 11008 KB Output isn't correct
3 Halted 0 ms 0 KB -