Submission #477920

#	Time	Username	Problem	Language	Result	Execution time	Memory
477920		stefantaga	Colors (RMI18_colors)	C++14	62 / 100	3067 ms	59192 KiB

colors

#include <bits/stdc++.h>

using namespace std;
int viz[150005],b[150005],a[150005],ok[150005],t,n,m,i,x,y,j,ok1;
int sal[150005],fr[150005],tata[150005],rang[150005],stanga,dreapta;
struct wow
{
    int x,y;
} muchii[200005];
vector <int> cinea[150005],cineb[150005];
vector <int> arb[800005];
int parinte (int x)
{
    if (x!=tata[x])
    {
        return parinte(tata[x]);
    }
    return x;
}
int q;
struct cetin
{
    int poz,rangpoz,tatapoz;
};
cetin baubau[800005];
void update(int st,int dr,int nod,int ua,int ub,int poz)
{
    if (ua<=st&&dr<=ub)
    {
        arb[nod].push_back(poz);
        return;
    }
    int mij=(st+dr)/2;
    if (ua<=mij)
    {
        update(st,mij,2*nod,ua,ub,poz);
    }
    if (mij<ub)
    {
        update(mij+1,dr,2*nod+1,ua,ub,poz);
    }
}
void uneste(int x,int y)
{
    x=parinte(x);
    y=parinte(y);
    if (rang[x]<rang[y])
    {
        baubau[++q]=cetin{x,rang[x],tata[x]};
        tata[x]=tata[y];
    }
    else if (rang[x]>rang[y])
    {
        baubau[++q]=cetin{y,rang[y],tata[y]};
        tata[y]=tata[x];
    }
    else if (rang[x]==rang[y])
    {
        baubau[++q]=cetin{x,rang[x],tata[x]};
        tata[x]=tata[y];
    }
}
int numar=0;
void dfs(int st,int dr,int nod)
{
    int salut2=0;
    for (int i=0; i<arb[nod].size(); i++)
    {
        int x=muchii[arb[nod][i]].x;
        int y=muchii[arb[nod][i]].y;
        if (parinte(x)!=parinte(y))
        {
            salut2++;
            uneste(x,y);
        }
    }
    if (st==dr)
    {
        int i;
        for (i=0; i<cinea[st].size(); i++)
        {
            fr[parinte(cinea[st][i])]++;
        }
        for (i=0; i<cineb[st].size(); i++)
        {
            if (fr[parinte(cineb[st][i])]!=0)
            {
                numar++;
            }
        }
        for (i=0; i<cinea[st].size(); i++)
        {
            fr[parinte(cinea[st][i])]--;
        }
        for (int i=salut2; i>=1; i--)
        {
            int pozitie=baubau[q].poz;
            tata[pozitie]=baubau[q].tatapoz;
            rang[pozitie]=baubau[q].rangpoz;
            q--;
        }
        return;
    }
    int mij=(st+dr)/2;
    dfs(st,mij,2*nod);
    dfs(mij+1,dr,2*nod+1);
    for (int i=salut2; i>=1; i--)
    {
        int pozitie=baubau[q].poz;
        tata[pozitie]=baubau[q].tatapoz;
        rang[pozitie]=baubau[q].rangpoz;
        q--;
    }
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>t;
    for (; t--;)
    {
        cin>>n>>m;
        for (i=1; i<=n; i++)
        {
            cin>>a[i];
        }
        for (i=1; i<=n; i++)
        {
            cin>>b[i];
        }
        ok1=1;
        for (i=1; i<=n; i++)
        {
            tata[i]=i;
            rang[i]=1;
            fr[i]=0;
        }
        for (i=1; i<=n; i++)
        {
            cinea[i].clear();
            cineb[i].clear();
        }
        for (i=1; i<=n; i++)
        {
            cinea[a[i]].push_back(i);
            cineb[b[i]].push_back(i);
        }
        for (i=1; i<=4*n; i++)
        {
            arb[i].clear();
        }
        for (i=1; i<=m; i++)
        {
            cin>>muchii[i].x>>muchii[i].y;
        }
        for (i=1; i<=n; i++)
        {
            if (b[i]>a[i])
            {
                cout<<"0"<<'\n';
                ok1=0;
                break;
            }
        }
        if (ok1==0)
        {
            continue;
        }
        for (i=1; i<=m; i++)
        {
            x=muchii[i].x;
            y=muchii[i].y;
            stanga=max(b[x],b[y]);
            dreapta=min(a[x],a[y]);
            update(1,n,1,stanga,dreapta,i);
        }
        numar=0;
        q=0;
        dfs(1,n,1);
        if (numar!=n)
        {
            cout<<"0"<<'\n';
        }
        else
        {
            cout<<"1"<<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

colors.cpp: In function 'void dfs(int, int, int)':
colors.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i=0; i<arb[nod].size(); i++)
      |                   ~^~~~~~~~~~~~~~~~
colors.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (i=0; i<cinea[st].size(); i++)
      |                   ~^~~~~~~~~~~~~~~~~
colors.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (i=0; i<cineb[st].size(); i++)
      |                   ~^~~~~~~~~~~~~~~~~
colors.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (i=0; i<cinea[st].size(); i++)
      |                   ~^~~~~~~~~~~~~~~~~

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