oj.uz

Submission #307504

# Submission time Handle Problem Language Result Execution time Memory
307504 2020-09-28T11:40:09 Z bigDuck Colors (RMI18_colors) C++14
100 / 100
 1211 ms 179128 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; q1.u=q0.u; q1.v=q0.v; q1.l=q0.l; q1.r=q0.r;
 q1.r=min(q1.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 82 ms 21632 KB Output is correct
2 Correct 40 ms 21880 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 22264 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 21624 KB Output is correct
2 Correct 43 ms 21632 KB Output is correct
3 Correct 19 ms 22144 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 21624 KB Output is correct
2 Correct 43 ms 21632 KB Output is correct
3 Correct 19 ms 22144 KB Output is correct
4 Correct 177 ms 21752 KB Output is correct
5 Correct 700 ms 67192 KB Output is correct
6 Correct 1211 ms 128576 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21632 KB Output is correct
2 Correct 40 ms 21880 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 88 ms 21624 KB Output is correct
5 Correct 43 ms 21632 KB Output is correct
6 Correct 19 ms 22144 KB Output is correct
7 Correct 87 ms 21624 KB Output is correct
8 Correct 43 ms 21760 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 163 ms 21752 KB Output is correct
2 Correct 681 ms 71160 KB Output is correct
3 Correct 631 ms 82376 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 29 ms 23040 KB Output is correct
3 Correct 20 ms 22016 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21632 KB Output is correct
2 Correct 40 ms 21880 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 90 ms 22264 KB Output is correct
5 Correct 88 ms 21624 KB Output is correct
6 Correct 43 ms 21632 KB Output is correct
7 Correct 19 ms 22144 KB Output is correct
8 Correct 177 ms 21752 KB Output is correct
9 Correct 700 ms 67192 KB Output is correct
10 Correct 1211 ms 128576 KB Output is correct
11 Correct 87 ms 21624 KB Output is correct
12 Correct 43 ms 21760 KB Output is correct
13 Correct 18 ms 22272 KB Output is correct
14 Correct 163 ms 21752 KB Output is correct
15 Correct 681 ms 71160 KB Output is correct
16 Correct 631 ms 82376 KB Output is correct
17 Correct 50 ms 21888 KB Output is correct
18 Correct 29 ms 23040 KB Output is correct
19 Correct 20 ms 22016 KB Output is correct
20 Correct 125 ms 22904 KB Output is correct
21 Correct 662 ms 78096 KB Output is correct
22 Correct 1114 ms 179128 KB Output is correct