Submission #306974

#	Time	Username	Problem	Language	Result	Execution time	Memory
306974		bigDuck	Colors (RMI18_colors)	C++14	17 / 100	353 ms	11776 KiB

colors

#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;
}

• Subtask 1: 0 / 15
• Subtask 2: 7 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 10 / 10
• Subtask 8: 0 / 22