oj.uz

답안 #230639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230639 2020-05-10T16:56:45 Z 2fat2code Colors (RMI18_colors) C++17
22 / 100
 155 ms 27000 KB 
/* 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[it.fr.fr]-=it.sc;
        par[it.fr.fr]=par[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';
    }
}

Compilation message

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 26616 KB Output is correct
2 Correct 45 ms 25856 KB Output is correct
3 Correct 23 ms 25856 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 27000 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 26616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 26616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 26616 KB Output is correct
2 Correct 45 ms 25856 KB Output is correct
3 Correct 23 ms 25856 KB Output is correct
4 Incorrect 90 ms 26616 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 155 ms 26840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 26108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 26616 KB Output is correct
2 Correct 45 ms 25856 KB Output is correct
3 Correct 23 ms 25856 KB Output is correct
4 Correct 86 ms 27000 KB Output is correct
5 Incorrect 90 ms 26616 KB Output isn't correct
6 Halted 0 ms 0 KB -