제출 #307170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
307170		bigDuck	Colors (RMI18_colors)	C++14	17 / 100	244 ms	11260 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 ts, 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);
if(res==false){return false;}else{return true;}
}





int32_t main(){
INIT
cin>>ts;

while(ts--){
    q.clear();
    while(!st.empty()){st.pop();}
    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;}
    }
    if(res==false){
    cout<<"0\n";}
    else{
        cout<<"1\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