oj.uz

Submission #1112702

# Submission time Handle Problem Language Result Execution time Memory
1112702 2024-11-14T15:46:22 Z Bananabread Colors (RMI18_colors) C++17
62 / 100
 3000 ms 62644 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);
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroint-loops")
using namespace std;
ll n,m,x;
vector<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_back({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.back();
    st.pop_back();
    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();
}

Compilation message

colors.cpp:18:37: warning: bad option '-funroint-loops' to pragma 'optimize' [-Wpragmas]
   18 | #pragma GCC optimize("unroint-loops")
      |                                     ^
colors.cpp:30:17: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   30 | ll find_par(ll u){
      |                 ^
colors.cpp:33:19: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   33 | bool uni(ll u,ll v){
      |                   ^
colors.cpp:43:15: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   43 | void rollback(){
      |               ^
colors.cpp:52:46: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   52 | void upd(ll pos,ll l,ll r,ll u,ll v,ll x,ll y){
      |                                              ^
colors.cpp:61:26: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   61 | void dfs(ll pos,ll l,ll r){
      |                          ^
colors.cpp:95:12: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
   95 | void solve(){
      |            ^
colors.cpp:144:10: warning: bad option '-funroint-loops' to attribute 'optimize' [-Wattributes]
  144 | int main(){
      |          ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 22600 KB Output is correct
2 Correct 43 ms 21584 KB Output is correct
3 Correct 43 ms 21884 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 23368 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 22772 KB Output is correct
2 Correct 32 ms 22108 KB Output is correct
3 Correct 18 ms 21840 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 22772 KB Output is correct
2 Correct 32 ms 22108 KB Output is correct
3 Correct 18 ms 21840 KB Output is correct
4 Correct 109 ms 23400 KB Output is correct
5 Correct 273 ms 38140 KB Output is correct
6 Correct 471 ms 62644 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 22600 KB Output is correct
2 Correct 43 ms 21584 KB Output is correct
3 Correct 43 ms 21884 KB Output is correct
4 Correct 60 ms 22772 KB Output is correct
5 Correct 32 ms 22108 KB Output is correct
6 Correct 18 ms 21840 KB Output is correct
7 Correct 66 ms 21584 KB Output is correct
8 Correct 39 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 115 ms 22240 KB Output is correct
2 Correct 1682 ms 42452 KB Output is correct
3 Execution timed out 3033 ms 52128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 22200 KB Output is correct
2 Correct 32 ms 22352 KB Output is correct
3 Correct 31 ms 21840 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 22600 KB Output is correct
2 Correct 43 ms 21584 KB Output is correct
3 Correct 43 ms 21884 KB Output is correct
4 Correct 77 ms 23368 KB Output is correct
5 Correct 60 ms 22772 KB Output is correct
6 Correct 32 ms 22108 KB Output is correct
7 Correct 18 ms 21840 KB Output is correct
8 Correct 109 ms 23400 KB Output is correct
9 Correct 273 ms 38140 KB Output is correct
10 Correct 471 ms 62644 KB Output is correct
11 Correct 66 ms 21584 KB Output is correct
12 Correct 39 ms 21584 KB Output is correct
13 Correct 23 ms 21840 KB Output is correct
14 Correct 115 ms 22240 KB Output is correct
15 Correct 1682 ms 42452 KB Output is correct
16 Execution timed out 3033 ms 52128 KB Time limit exceeded
17 Halted 0 ms 0 KB -