oj.uz

Submission #1112699

# Submission time Handle Problem Language Result Execution time Memory
1112699 2024-11-14T15:27:35 Z Bananabread Colors (RMI18_colors) C++17
62 / 100
 3000 ms 58976 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,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 65 ms 21584 KB Output is correct
2 Correct 45 ms 21584 KB Output is correct
3 Correct 49 ms 21896 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21832 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 21752 KB Output is correct
2 Correct 33 ms 21584 KB Output is correct
3 Correct 17 ms 21840 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 21752 KB Output is correct
2 Correct 33 ms 21584 KB Output is correct
3 Correct 17 ms 21840 KB Output is correct
4 Correct 111 ms 21584 KB Output is correct
5 Correct 312 ms 37540 KB Output is correct
6 Correct 510 ms 58976 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21584 KB Output is correct
2 Correct 45 ms 21584 KB Output is correct
3 Correct 49 ms 21896 KB Output is correct
4 Correct 60 ms 21752 KB Output is correct
5 Correct 33 ms 21584 KB Output is correct
6 Correct 17 ms 21840 KB Output is correct
7 Correct 68 ms 21584 KB Output is correct
8 Correct 36 ms 21584 KB Output is correct
9 Correct 23 ms 21840 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 21644 KB Output is correct
2 Correct 1611 ms 38948 KB Output is correct
3 Execution timed out 3056 ms 44764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 21584 KB Output is correct
2 Correct 31 ms 22056 KB Output is correct
3 Correct 30 ms 21596 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21584 KB Output is correct
2 Correct 45 ms 21584 KB Output is correct
3 Correct 49 ms 21896 KB Output is correct
4 Correct 73 ms 21832 KB Output is correct
5 Correct 60 ms 21752 KB Output is correct
6 Correct 33 ms 21584 KB Output is correct
7 Correct 17 ms 21840 KB Output is correct
8 Correct 111 ms 21584 KB Output is correct
9 Correct 312 ms 37540 KB Output is correct
10 Correct 510 ms 58976 KB Output is correct
11 Correct 68 ms 21584 KB Output is correct
12 Correct 36 ms 21584 KB Output is correct
13 Correct 23 ms 21840 KB Output is correct
14 Correct 118 ms 21644 KB Output is correct
15 Correct 1611 ms 38948 KB Output is correct
16 Execution timed out 3056 ms 44764 KB Time limit exceeded
17 Halted 0 ms 0 KB -