oj.uz

Submission #477920

# Submission time Handle Problem Language Result Execution time Memory
477920 2021-10-04T15:39:52 Z stefantaga Colors (RMI18_colors) C++14
62 / 100
 3000 ms 59192 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 84 ms 26212 KB Output is correct
2 Correct 49 ms 26232 KB Output is correct
3 Correct 51 ms 26400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 26256 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 26200 KB Output is correct
2 Correct 38 ms 26220 KB Output is correct
3 Correct 17 ms 26288 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 26200 KB Output is correct
2 Correct 38 ms 26220 KB Output is correct
3 Correct 17 ms 26288 KB Output is correct
4 Correct 163 ms 26468 KB Output is correct
5 Correct 439 ms 41120 KB Output is correct
6 Correct 700 ms 59192 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 26212 KB Output is correct
2 Correct 49 ms 26232 KB Output is correct
3 Correct 51 ms 26400 KB Output is correct
4 Correct 89 ms 26200 KB Output is correct
5 Correct 38 ms 26220 KB Output is correct
6 Correct 17 ms 26288 KB Output is correct
7 Correct 90 ms 26200 KB Output is correct
8 Correct 50 ms 26196 KB Output is correct
9 Correct 22 ms 26384 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 26224 KB Output is correct
2 Correct 2024 ms 43468 KB Output is correct
3 Execution timed out 3067 ms 48788 KB Time limit exceeded

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 26244 KB Output is correct
2 Correct 30 ms 26452 KB Output is correct
3 Correct 33 ms 26312 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 26212 KB Output is correct
2 Correct 49 ms 26232 KB Output is correct
3 Correct 51 ms 26400 KB Output is correct
4 Correct 89 ms 26256 KB Output is correct
5 Correct 89 ms 26200 KB Output is correct
6 Correct 38 ms 26220 KB Output is correct
7 Correct 17 ms 26288 KB Output is correct
8 Correct 163 ms 26468 KB Output is correct
9 Correct 439 ms 41120 KB Output is correct
10 Correct 700 ms 59192 KB Output is correct
11 Correct 90 ms 26200 KB Output is correct
12 Correct 50 ms 26196 KB Output is correct
13 Correct 22 ms 26384 KB Output is correct
14 Correct 163 ms 26224 KB Output is correct
15 Correct 2024 ms 43468 KB Output is correct
16 Execution timed out 3067 ms 48788 KB Time limit exceeded