Submission #230651

#	Time	Username	Problem	Language	Result	Execution time	Memory
230651		2fat2code	Colors (RMI18_colors)	C++17	100 / 100	1075 ms	129200 KiB

colors

/* ok this problem is marvelous */
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

int t,n,m,a[150005],b[150005],par[150005],siz[150005],ans;
vector<pair<pair<int,int>,int>>DSU;
vector<pair<int,int>>tree[4*150005];
vector<int>A[150005],B[150005];
vector<int>nod[150005];
bitset<150005>viz;

void update(int l,int r,int le,int ri,pair<int,int>pi,int nod){
    if(l>ri || r<le) return;
    else if(l>=le && r<=ri) tree[nod].push_back(pi);
    else{
        int mid=l+(r-l)/2;
        update(l,mid,le,ri,pi,2*nod);
        update(mid+1,r,le,ri,pi,2*nod+1);
    }
}

int findpar(int x){
    if(x!=par[x]){
        DSU.push_back({{x,par[x]},0});
        par[x]=findpar(par[x]);
    }
    return par[x];
}

int join(int x,int y){
    int x1=findpar(x);
    int y1=findpar(y);
    if(x1!=y1){
        if(siz[x1]<siz[y1]) swap(x1,y1);
        DSU.push_back({{y1,par[y1]},siz[y1]});
        par[y1]=x1;
        siz[x1]+=siz[y1];
    }
}

void remov(int x){
    while(DSU.size()>x){
        auto it=DSU.back();
        DSU.pop_back();
        siz[par[it.fr.fr]]-=it.sc;
        par[it.fr.fr]=it.fr.sc;
    }
}

void solve(int l,int r,int nod){
    int sz=DSU.size();
    for(auto it:tree[nod]){
        join(it.fr,it.sc);
    }
    if(l==r){
        for(auto it:A[l]) viz[findpar(it)]=1;
        for(auto it:B[l]){
            if(viz[findpar(it)]==0) ans=0;
        }
        for(auto it:A[l]) viz[findpar(it)]=0;
    }
    else{
        int mid=l+(r-l)/2;
        solve(l,mid,2*nod);
        solve(mid+1,r,2*nod+1);
    }
    remov(sz);
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> t;
    while(t--){
        ans=1;
        cin >> n >> m;
        for(int i=1;i<=n;i++) par[i]=i,siz[i]=1;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            A[a[i]].push_back(i);
        }
        for(int i=1;i<=n;i++){
            cin >> b[i];
            B[b[i]].push_back(i);
        }
        for(int i=1;i<=m;i++){
            int x,y;
            cin >> x >> y;
            nod[x].push_back(y);
            nod[y].push_back(x);
            if(max(b[x],b[y])<=min(a[x],a[y])) update(1,n,max(b[x],b[y]),min(a[x],a[y]),{x,y},1);
        }
        solve(1,n,1);
        cout << ans << '\n';
        DSU.clear();
        for(int i=1;i<=n;i++){
            par[i]=0,siz[i]=0;
            A[i].clear();
            B[i].clear();
            nod[i].clear();
        }
        for(int i=1;i<=4*n;i++) tree[i].clear();
    }
}

Compilation message (stderr)

colors.cpp: In function 'long long int join(long long int, long long int)':
colors.cpp:50:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
colors.cpp: In function 'void remov(long long int)':
colors.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(DSU.size()>x){
           ~~~~~~~~~~^~

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22