oj.uz

Submission #1112712

# Submission time Handle Problem Language Result Execution time Memory
1112712 2024-11-14T16:26:45 Z Bananabread Colors (RMI18_colors) C++17
100 / 100
 497 ms 118896 KB 
#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "temp"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll n,m,x;
stack<array<ll,4>> st;
vector<pair<ll,ll>>  segtree[600001];
vector<ll> colors[150001],need[150001];
ll par[150001];
ll sz[150001];
ll a[150001];
ll b[150001];
ll check[150001];
ll ans;
ll find_par(ll u){
    return (u==par[u] ? u: find_par(par[u]));
}
bool uni(ll u,ll v){
    u=find_par(u);
    v=find_par(v);
    if(u==v) return 0;
    if(sz[u]>sz[v]) swap(u,v);
    st.push({u,sz[u],v,sz[v]});
    par[u]=v;
    sz[v]+=sz[u];
    return 1;
}
void rollback(){
    if(st.size()==0) return ;
    array<ll,4> c=st.top();
    st.pop();
    par[c[0]]=c[0];
    par[c[2]]=c[2];
    sz[c[0]]=c[1];
    sz[c[2]]=c[3];
}
void upd(ll pos,ll l,ll r,ll u,ll v,ll x,ll y){
    if(u>v) return ;
    if(u<=l&&r<=v) segtree[pos].push_back({x,y});
    else if(l>v||r<u) return ;
    else{
        ll mid=(l+r)/2;
        upd(2*pos,l,mid,u,v,x,y);
        upd(2*pos+1,mid+1,r,u,v,x,y);
    }
}
void dfs(ll pos,ll l,ll r){
    ll cnt=0;
    for(auto [u,v]:segtree[pos]){
        cnt+=uni(u,v);
//        cout<<"+ "<<u<<' '<<v<<ntr;
    }
    if(l==r){
        ll col=l;
        for(auto i:colors[col]){
            ll p=find_par(i);
            check[p]=1;
        }
        for(auto i:need[col]){
            ll p=find_par(i);
            if(!check[p]) ans=0;
        }
        for(auto i:colors[col]){
            ll p=find_par(i);
            check[p]=0;
        }
        //cout<<l<<' '<<ans<<ntr;
    }
    else{
        ll mid=(l+r)/2;
        dfs(2*pos,l,mid);
        dfs(2*pos+1,mid+1,r);
        segtree[pos]={};
    }
    for(int i=1;i<=cnt;i++){
        rollback();
//        cout<<"- "<<u<<' '<<v<<ntr;
    }
    segtree[pos]={};
}
void solve(){
    ans=1;
    st={};
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        par[i]=i;
        sz[i]=1;
        colors[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        need[b[i]].push_back(i);
    }

    vector<pair<ll,ll>> edges;
    for(int i=1;i<=m;i++){
        ll u,v;
        cin>>u>>v;
        edges.push_back({u,v});
    }
//    if(x==47){
//        cerr<<n<<' '<<m<<ntr;
//        for(int i=1;i<=n;i++) cerr<<a[i]<<' ';
//        cerr<<ntr;
//        for(int i=1;i<=n;i++) cerr<<b[i]<<' ';
//        cerr<<ntr;
//        for(auto [u,v]:edges) cerr<<u<<' '<<v<<ntr;
//    }
    for(int i=1;i<=n;i++){
        if(a[i]<b[i]){
            ans=0;
        }
    }
    if(ans==0){
        for(int i=1;i<=n;i++) colors[i]={},need[i]={};
        cout<<0<<ntr;
        return ;
    }
    for(auto [u,v]:edges){
//        cout<<max(b[u],b[v])<<' '<<min(a[u],a[v])<<ntr;
        upd(1,1,n,max(b[u],b[v]),min(a[u],a[v]),u,v);
    }
//    cout<<ntr;
    dfs(1,1,n);
    for(int i=1;i<=n;i++) colors[i]={},need[i]={};

    cout<<ans<<ntr;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    ll t;
    cin>>t;
    for(x=1;x<=t;x++)
        solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27360 KB Output is correct
2 Correct 19 ms 27468 KB Output is correct
3 Correct 7 ms 25680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 27636 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 25168 KB Output is correct
2 Correct 21 ms 21712 KB Output is correct
3 Correct 9 ms 22012 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 25168 KB Output is correct
2 Correct 21 ms 21712 KB Output is correct
3 Correct 9 ms 22012 KB Output is correct
4 Correct 94 ms 21584 KB Output is correct
5 Correct 293 ms 49928 KB Output is correct
6 Correct 463 ms 88460 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27360 KB Output is correct
2 Correct 19 ms 27468 KB Output is correct
3 Correct 7 ms 25680 KB Output is correct
4 Correct 46 ms 25168 KB Output is correct
5 Correct 21 ms 21712 KB Output is correct
6 Correct 9 ms 22012 KB Output is correct
7 Correct 48 ms 21584 KB Output is correct
8 Correct 21 ms 23120 KB Output is correct
9 Correct 8 ms 22096 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21712 KB Output is correct
2 Correct 265 ms 53560 KB Output is correct
3 Correct 269 ms 64252 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21840 KB Output is correct
2 Correct 15 ms 24068 KB Output is correct
3 Correct 8 ms 25424 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27360 KB Output is correct
2 Correct 19 ms 27468 KB Output is correct
3 Correct 7 ms 25680 KB Output is correct
4 Correct 51 ms 27636 KB Output is correct
5 Correct 46 ms 25168 KB Output is correct
6 Correct 21 ms 21712 KB Output is correct
7 Correct 9 ms 22012 KB Output is correct
8 Correct 94 ms 21584 KB Output is correct
9 Correct 293 ms 49928 KB Output is correct
10 Correct 463 ms 88460 KB Output is correct
11 Correct 48 ms 21584 KB Output is correct
12 Correct 21 ms 23120 KB Output is correct
13 Correct 8 ms 22096 KB Output is correct
14 Correct 101 ms 21712 KB Output is correct
15 Correct 265 ms 53560 KB Output is correct
16 Correct 269 ms 64252 KB Output is correct
17 Correct 27 ms 21840 KB Output is correct
18 Correct 15 ms 24068 KB Output is correct
19 Correct 8 ms 25424 KB Output is correct
20 Correct 68 ms 28036 KB Output is correct
21 Correct 302 ms 59668 KB Output is correct
22 Correct 497 ms 118896 KB Output is correct