oj.uz

Submission #307546

# Submission time Handle Problem Language Result Execution time Memory
307546 2020-09-28T15:05:51 Z bigDuck Colors (RMI18_colors) C++14
100 / 100
 879 ms 105920 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((tl>q0.r) || (tr<q0.l)){return;}
if( (tl>=q0.l) && (tr<=q0.r) ){
    seg[nod].pb(q0); return;
}
if(tl==tr){return;}
int med=(tl+tr)/2;
ins(nod*2, q0, tl, med);
ins(2*nod+1, q0, med+1, tr);
}


void clean(){
    for(int i=1; i<=4*n; i++){
        seg[i].clear();
    }
}



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();
}



return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21504 KB Output is correct
2 Correct 39 ms 21632 KB Output is correct
3 Correct 18 ms 22016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 21884 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 21504 KB Output is correct
2 Correct 43 ms 21504 KB Output is correct
3 Correct 20 ms 21888 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 21504 KB Output is correct
2 Correct 43 ms 21504 KB Output is correct
3 Correct 20 ms 21888 KB Output is correct
4 Correct 162 ms 21624 KB Output is correct
5 Correct 522 ms 46608 KB Output is correct
6 Correct 879 ms 79052 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21504 KB Output is correct
2 Correct 39 ms 21632 KB Output is correct
3 Correct 18 ms 22016 KB Output is correct
4 Correct 85 ms 21504 KB Output is correct
5 Correct 43 ms 21504 KB Output is correct
6 Correct 20 ms 21888 KB Output is correct
7 Correct 87 ms 21504 KB Output is correct
8 Correct 41 ms 21632 KB Output is correct
9 Correct 19 ms 21888 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 21752 KB Output is correct
2 Correct 509 ms 48468 KB Output is correct
3 Correct 503 ms 57688 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 21752 KB Output is correct
2 Correct 27 ms 22272 KB Output is correct
3 Correct 20 ms 21760 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21504 KB Output is correct
2 Correct 39 ms 21632 KB Output is correct
3 Correct 18 ms 22016 KB Output is correct
4 Correct 85 ms 21884 KB Output is correct
5 Correct 85 ms 21504 KB Output is correct
6 Correct 43 ms 21504 KB Output is correct
7 Correct 20 ms 21888 KB Output is correct
8 Correct 162 ms 21624 KB Output is correct
9 Correct 522 ms 46608 KB Output is correct
10 Correct 879 ms 79052 KB Output is correct
11 Correct 87 ms 21504 KB Output is correct
12 Correct 41 ms 21632 KB Output is correct
13 Correct 19 ms 21888 KB Output is correct
14 Correct 154 ms 21752 KB Output is correct
15 Correct 509 ms 48468 KB Output is correct
16 Correct 503 ms 57688 KB Output is correct
17 Correct 48 ms 21752 KB Output is correct
18 Correct 27 ms 22272 KB Output is correct
19 Correct 20 ms 21760 KB Output is correct
20 Correct 116 ms 22200 KB Output is correct
21 Correct 502 ms 52184 KB Output is correct
22 Correct 830 ms 105920 KB Output is correct