oj.uz

Submission #1112713

# Submission time Handle Problem Language Result Execution time Memory
1112713 2024-11-14T16:28:05 Z Bananabread Colors (RMI18_colors) C++17
100 / 100
 472 ms 77580 KB 
#include<bits/stdc++.h>
#define ll int
#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;
struct save{
    ll u,szu,v,szv;
};
vector<save> 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 (par[u]==u ? u : find_par(par[u]));
}
inline 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_back({u,sz[u],v,sz[v]});
    par[u]=v;
    sz[v]+=sz[u];
    return 1;
}
inline void rollback(){
    if(st.size()==0) return ;
    save c=st.back();
    st.pop_back();
    par[c.u]=c.u;
    par[c.v]=c.v;
    sz[c.u]=c.szu;
    sz[c.v]=c.szv;
}
void upd(ll pos,ll l,ll r,ll u,ll v,ll x,ll y){
    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)>>1;
        dfs(pos<<1,l,mid);
        dfs(pos<<1|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});
    }
    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){
        if(max(b[u],b[v])<=min(a[u],a[v])) upd(1,1,n,max(b[u],b[v]),min(a[u],a[v]),u,v);
    }
    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;
    while(t--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24392 KB Output is correct
2 Correct 18 ms 24568 KB Output is correct
3 Correct 9 ms 21840 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 24400 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 24372 KB Output is correct
2 Correct 22 ms 24400 KB Output is correct
3 Correct 9 ms 21840 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 24372 KB Output is correct
2 Correct 22 ms 24400 KB Output is correct
3 Correct 9 ms 21840 KB Output is correct
4 Correct 96 ms 21584 KB Output is correct
5 Correct 265 ms 39924 KB Output is correct
6 Correct 472 ms 58960 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24392 KB Output is correct
2 Correct 18 ms 24568 KB Output is correct
3 Correct 9 ms 21840 KB Output is correct
4 Correct 48 ms 24372 KB Output is correct
5 Correct 22 ms 24400 KB Output is correct
6 Correct 9 ms 21840 KB Output is correct
7 Correct 50 ms 21752 KB Output is correct
8 Correct 21 ms 24400 KB Output is correct
9 Correct 9 ms 22352 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 22352 KB Output is correct
2 Correct 246 ms 41304 KB Output is correct
3 Correct 245 ms 49540 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22444 KB Output is correct
2 Correct 13 ms 22788 KB Output is correct
3 Correct 10 ms 21584 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24392 KB Output is correct
2 Correct 18 ms 24568 KB Output is correct
3 Correct 9 ms 21840 KB Output is correct
4 Correct 56 ms 24400 KB Output is correct
5 Correct 48 ms 24372 KB Output is correct
6 Correct 22 ms 24400 KB Output is correct
7 Correct 9 ms 21840 KB Output is correct
8 Correct 96 ms 21584 KB Output is correct
9 Correct 265 ms 39924 KB Output is correct
10 Correct 472 ms 58960 KB Output is correct
11 Correct 50 ms 21752 KB Output is correct
12 Correct 21 ms 24400 KB Output is correct
13 Correct 9 ms 22352 KB Output is correct
14 Correct 93 ms 22352 KB Output is correct
15 Correct 246 ms 41304 KB Output is correct
16 Correct 245 ms 49540 KB Output is correct
17 Correct 25 ms 22444 KB Output is correct
18 Correct 13 ms 22788 KB Output is correct
19 Correct 10 ms 21584 KB Output is correct
20 Correct 64 ms 21984 KB Output is correct
21 Correct 239 ms 42660 KB Output is correct
22 Correct 385 ms 77580 KB Output is correct