oj.uz

Submission #1112698

# Submission time Handle Problem Language Result Execution time Memory
1112698 2024-11-14T15:26:20 Z Bananabread Colors (RMI18_colors) C++17
62 / 100
 3000 ms 95356 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 70 ms 23112 KB Output is correct
2 Correct 41 ms 22344 KB Output is correct
3 Correct 38 ms 22096 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 23112 KB Output is correct
2 Correct 32 ms 22192 KB Output is correct
3 Correct 17 ms 21896 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 23112 KB Output is correct
2 Correct 32 ms 22192 KB Output is correct
3 Correct 17 ms 21896 KB Output is correct
4 Correct 109 ms 24616 KB Output is correct
5 Correct 359 ms 56184 KB Output is correct
6 Correct 548 ms 95356 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23112 KB Output is correct
2 Correct 41 ms 22344 KB Output is correct
3 Correct 38 ms 22096 KB Output is correct
4 Correct 59 ms 23112 KB Output is correct
5 Correct 32 ms 22192 KB Output is correct
6 Correct 17 ms 21896 KB Output is correct
7 Correct 68 ms 22944 KB Output is correct
8 Correct 36 ms 22096 KB Output is correct
9 Correct 24 ms 22096 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 24816 KB Output is correct
2 Correct 1803 ms 58172 KB Output is correct
3 Execution timed out 3070 ms 61704 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22608 KB Output is correct
2 Correct 28 ms 22780 KB Output is correct
3 Correct 25 ms 22096 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23112 KB Output is correct
2 Correct 41 ms 22344 KB Output is correct
3 Correct 38 ms 22096 KB Output is correct
4 Correct 73 ms 23624 KB Output is correct
5 Correct 59 ms 23112 KB Output is correct
6 Correct 32 ms 22192 KB Output is correct
7 Correct 17 ms 21896 KB Output is correct
8 Correct 109 ms 24616 KB Output is correct
9 Correct 359 ms 56184 KB Output is correct
10 Correct 548 ms 95356 KB Output is correct
11 Correct 68 ms 22944 KB Output is correct
12 Correct 36 ms 22096 KB Output is correct
13 Correct 24 ms 22096 KB Output is correct
14 Correct 115 ms 24816 KB Output is correct
15 Correct 1803 ms 58172 KB Output is correct
16 Execution timed out 3070 ms 61704 KB Time limit exceeded
17 Halted 0 ms 0 KB -