oj.uz

Submission #1064969

# Submission time Handle Problem Language Result Execution time Memory
1064969 2024-08-18T20:26:05 Z AlgorithmWarrior Colors (RMI18_colors) C++14
0 / 100
 384 ms 524292 KB 
#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<=4*n;++i)
        aint[i].clear();
    for(i=1;i<=n;++i)
        nodes[i].clear();
    for(i=1;i<=n;++i)
    {
        cin>>v2[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);
    }
    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);
    }
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 252 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 254 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 254 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 384 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -