oj.uz

Submission #1112710

# Submission time Handle Problem Language Result Execution time Memory
1112710 2024-11-14T16:25:37 Z Bananabread Colors (RMI18_colors) C++17
100 / 100
 532 ms 126332 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<=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 44 ms 27216 KB Output is correct
2 Correct 19 ms 27352 KB Output is correct
3 Correct 8 ms 27728 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 27472 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 27216 KB Output is correct
2 Correct 22 ms 23632 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 50 ms 27216 KB Output is correct
2 Correct 22 ms 23632 KB Output is correct
3 Correct 9 ms 21840 KB Output is correct
4 Correct 100 ms 24392 KB Output is correct
5 Correct 334 ms 50176 KB Output is correct
6 Correct 532 ms 94864 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 27216 KB Output is correct
2 Correct 19 ms 27352 KB Output is correct
3 Correct 8 ms 27728 KB Output is correct
4 Correct 50 ms 27216 KB Output is correct
5 Correct 22 ms 23632 KB Output is correct
6 Correct 9 ms 21840 KB Output is correct
7 Correct 53 ms 26700 KB Output is correct
8 Correct 22 ms 23888 KB Output is correct
9 Correct 9 ms 23632 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 21752 KB Output is correct
2 Correct 326 ms 58164 KB Output is correct
3 Correct 308 ms 72716 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23468 KB Output is correct
2 Correct 14 ms 24280 KB Output is correct
3 Correct 8 ms 25680 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 27216 KB Output is correct
2 Correct 19 ms 27352 KB Output is correct
3 Correct 8 ms 27728 KB Output is correct
4 Correct 50 ms 27472 KB Output is correct
5 Correct 50 ms 27216 KB Output is correct
6 Correct 22 ms 23632 KB Output is correct
7 Correct 9 ms 21840 KB Output is correct
8 Correct 100 ms 24392 KB Output is correct
9 Correct 334 ms 50176 KB Output is correct
10 Correct 532 ms 94864 KB Output is correct
11 Correct 53 ms 26700 KB Output is correct
12 Correct 22 ms 23888 KB Output is correct
13 Correct 9 ms 23632 KB Output is correct
14 Correct 98 ms 21752 KB Output is correct
15 Correct 326 ms 58164 KB Output is correct
16 Correct 308 ms 72716 KB Output is correct
17 Correct 31 ms 23468 KB Output is correct
18 Correct 14 ms 24280 KB Output is correct
19 Correct 8 ms 25680 KB Output is correct
20 Correct 70 ms 26184 KB Output is correct
21 Correct 312 ms 63636 KB Output is correct
22 Correct 523 ms 126332 KB Output is correct