제출 #230641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230641		2fat2code	Colors (RMI18_colors)	C++17	100 / 100	1095 ms	136620 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,ans,par[150005],siz[150005],a[150005],b[150005];
vector<int>A[150005],B[150005];
vector<int>nod[150005];
vector<pair<int,int>>tree[4*150005];
vector<pair<pair<int,int>,int>>DSU;
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];
}

void conect(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 ers(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]){
        conect(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);
    }
    ers(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());
   // ifstream cin("input.in");
    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];
        for(int i=1;i<=n;i++){
            A[a[i]].push_back(i);
        }
        for(int i=1;i<=n;i++) cin >> b[i];
        for(int i=1;i<=n;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);
        for(int i=1;i<=n;i++) A[i].clear(),B[i].clear();
        DSU.clear();
        for(int i=1;i<=4*n;i++) tree[i].clear();
        for(int i=1;i<=n;i++) nod[i].clear();
        cout << ans << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

colors.cpp: In function 'void ers(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