제출 #1065498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065498		AlgorithmWarrior	Colors (RMI18_colors)	C++14	100 / 100	723 ms	68656 KiB

colors

#include <bits/stdc++.h>
#define MAX 150005

using namespace std;

int v1[MAX],v2[MAX];
set<int>cul;
vector<int>aint[4*MAX];
bool activ[MAX];
vector<int>nodes[MAX];
vector<int>G[MAX];
int tata[MAX],rnk[MAX],minim[MAX];
struct str
{
    int a,b,c,d;
};
stack<str>stv;

void add(int nod,int st,int dr,int a,int b,int val)
{
    if(a<=st && dr<=b)
        aint[nod].push_back(val);
    else
    {
        int mij=(st+dr)/2;
        if(a<=mij)
            add(2*nod,st,mij,a,b,val);
        if(b>mij)
            add(2*nod+1,mij+1,dr,a,b,val);
    }
}

int root(int nod)
{
    if(tata[nod])
        return root(tata[nod]);
    return nod;
}

bool DSU(int nod1,int nod2)
{
    int r1=root(nod1);
    int r2=root(nod2);
    if(r1==r2)
        return 0;
    if(rnk[r1]<rnk[r2])
        swap(r1,r2);
    stv.push({r1,rnk[r1],minim[r1],r2});
    rnk[r1]=max(rnk[r1],rnk[r2]+1);
    tata[r2]=r1;
    minim[r1]=min(minim[r1],minim[r2]);
    return 1;
}

void dfs(int nod,int st,int dr,bool& rasp)
{
    int cnt=0;
    for(auto act : aint[nod])
    {
        activ[act]=1;
        for(auto vec : G[act])
            if(activ[vec])
                cnt+=DSU(act,vec);
    }
    if(st==dr)
    {
        for(auto nd : nodes[st])
            if(minim[root(nd)]>st)
                rasp=0;
    }
    else
    {
        int mij=(st+dr)/2;
        dfs(2*nod+1,mij+1,dr,rasp);
        dfs(2*nod,st,mij,rasp);
    }
    for(auto act : aint[nod])
        activ[act]=0;
    while(cnt--)
    {
        str bck=stv.top(); stv.pop();
        rnk[bck.a]=bck.b;
        tata[bck.d]=0;
        minim[bck.a]=bck.c;
    }
}

bool solve()
{
    int n,m;
    cin>>n>>m;
    fill(activ+1,activ+n+1,0);
    fill(tata+1,tata+n+1,0);
    fill(rnk+1,rnk+n+1,0);
    int i;
    cul.clear();
    for(i=1;i<=n;++i)
    {
        cin>>v1[i];
        cul.insert(v1[i]);
        minim[i]=v1[i];
    }
    for(i=1;i<=n;++i)
        cin>>v2[i];
    for(i=1;i<=n;++i)
        G[i].clear();
    for(i=1;i<=m;++i)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(i=1;i<=4*n;++i)
        aint[i].clear();
    for(i=1;i<=n;++i)
        nodes[i].clear();
    for(i=1;i<=n;++i)
    {
        if(cul.find(v2[i])==cul.end() || v1[i]<v2[i])
            return 0;
        add(1,1,n,v2[i],v1[i],i);
        nodes[v2[i]].push_back(i);
    }
    bool rasp=1;
    dfs(1,1,n,rasp);
    return rasp;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
        cout<<solve()<<'\n';
    return 0;
}

• 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