oj.uz

Submission #307502

# Submission time Handle Problem Language Result Execution time Memory
307502 2020-09-28T11:37:10 Z bigDuck Colors (RMI18_colors) C++14
100 / 100
 1199 ms 186268 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 ts, n, m, k, a[150010], b[150010], q, l, r;
vector<int> oa[150010], ob[150010];

struct query{
int l, r, u, v;
};
vector<query> seg[600010];



struct DSU{
int ptr[150010], sz[150010]; bool mrk[150010];
};
DSU dsu;


struct ch{
int u, v, t;
};
stack<ch> st;


int find_root(int x){ int cr=x; while(dsu.ptr[cr]!=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);
    }

}

void separ(int u, int v){
dsu.ptr[v]=v; dsu.sz[u]-=dsu.sz[v];
return;
}

void roll_back(int t){
    while((!st.empty()) && ( ((st.top()).t)>=t)){
        auto c=st.top(); st.pop(); separ(c.u, c.v);
    }
    return;
}




void ins(int nod, query q0, int tl, int tr){
if(q0.l>q0.r){return;}

if( (tl==q0.l) && (tr==q0.r) ){
    seg[nod].pb(q0); return;
}

int med=(tl+tr)/2;
query q1=q0; q1.r=min(q0.r,med);
ins(nod*2, q1, tl, med);
q1.r=q0.r; q1.l=max(med+1, q0.l);
ins(2*nod+1, q1, med+1, tr);
}


void clean(int nod, int tl , int tr){
    int med=(tl+tr)/2;
seg[nod].clear(); if(tl==tr){return;} clean(nod*2, tl, med); clean(nod*2+1, med+1, tr);
}



bool rec(int nod, int tl, int tr, int t){
 bool res=true;
for(auto q0:seg[nod]){
    unite(q0.u, q0.v, t);
}
if(tl==tr){
    for(auto u:oa[tl]){
        int rt=find_root(u);
        dsu.mrk[rt]=true;
    }
    for(auto u:ob[tl]){
        int rt=find_root(u);
        if(!dsu.mrk[rt]){res=false; break;}
    }
    for(auto u:oa[tl]){
        int rt=find_root(u);
        dsu.mrk[rt]=false;
    }
    roll_back(t);
    return res;
}

int med=(tl+tr)/2;

bool r1=rec(nod*2, tl, med, t+1);
bool r2=rec(nod*2+1, med+1, tr, t+1);
roll_back(t);
return (r1&&r2);
}





int32_t main(){
INIT
cin>>ts;


while(ts--){
    cin>>n>>m;

    for(int i=1; i<=n; i++){dsu.ptr[i]=i; dsu.sz[i]=1; dsu.mrk[i]=false;}

    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;
        query q0; q0.u=u; q0.v=v; q0.l=max(b[u], b[v]); q0.r=min(a[u], a[v]);
        ins(1, q0, 1, n);
    }
    bool res=rec(1, 1, n, 1);
    for(int i=1; i<=n;i++){
        if(a[i]<b[i]){res=false; break;}
    }
    cout<<res<<"\n";
    for(int i=1; i<=n; i++){ oa[i].clear(); ob[i].clear();}
    clean(1, 1, n);
}



return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 21632 KB Output is correct
2 Correct 40 ms 21880 KB Output is correct
3 Correct 18 ms 22400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 22136 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21624 KB Output is correct
2 Correct 44 ms 22272 KB Output is correct
3 Correct 19 ms 22272 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21624 KB Output is correct
2 Correct 44 ms 22272 KB Output is correct
3 Correct 19 ms 22272 KB Output is correct
4 Correct 178 ms 24728 KB Output is correct
5 Correct 729 ms 73616 KB Output is correct
6 Correct 1199 ms 135224 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 21632 KB Output is correct
2 Correct 40 ms 21880 KB Output is correct
3 Correct 18 ms 22400 KB Output is correct
4 Correct 93 ms 21624 KB Output is correct
5 Correct 44 ms 22272 KB Output is correct
6 Correct 19 ms 22272 KB Output is correct
7 Correct 89 ms 23160 KB Output is correct
8 Correct 43 ms 22272 KB Output is correct
9 Correct 18 ms 22272 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 21752 KB Output is correct
2 Correct 695 ms 76900 KB Output is correct
3 Correct 642 ms 89512 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 21888 KB Output is correct
2 Correct 28 ms 23424 KB Output is correct
3 Correct 20 ms 22144 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 21632 KB Output is correct
2 Correct 40 ms 21880 KB Output is correct
3 Correct 18 ms 22400 KB Output is correct
4 Correct 91 ms 22136 KB Output is correct
5 Correct 93 ms 21624 KB Output is correct
6 Correct 44 ms 22272 KB Output is correct
7 Correct 19 ms 22272 KB Output is correct
8 Correct 178 ms 24728 KB Output is correct
9 Correct 729 ms 73616 KB Output is correct
10 Correct 1199 ms 135224 KB Output is correct
11 Correct 89 ms 23160 KB Output is correct
12 Correct 43 ms 22272 KB Output is correct
13 Correct 18 ms 22272 KB Output is correct
14 Correct 166 ms 21752 KB Output is correct
15 Correct 695 ms 76900 KB Output is correct
16 Correct 642 ms 89512 KB Output is correct
17 Correct 50 ms 21888 KB Output is correct
18 Correct 28 ms 23424 KB Output is correct
19 Correct 20 ms 22144 KB Output is correct
20 Correct 127 ms 25208 KB Output is correct
21 Correct 674 ms 84164 KB Output is correct
22 Correct 1132 ms 186268 KB Output is correct