oj.uz

Submission #225388

# Submission time Handle Problem Language Result Execution time Memory
225388 2020-04-20T12:53:56 Z nicolaalexandra Colors (RMI18_colors) C++14
52 / 100
 3000 ms 39612 KB 
#include <bits/stdc++.h>
#define DIM 150010
#define INF 2000000000
using namespace std;
vector <int> L[DIM],poz[DIM*4];
int a[DIM],b[DIM],f[DIM],f2[DIM],c[DIM],v[DIM],viz[DIM];
int t,n,m,i,j,x,y,k,sol,mini,maxi,ok,g;
struct seg_tree{
    int minia,maxib;
} aint[4*DIM];
void dfs (int nod){
    viz[nod] = 1;
    v[++k] = nod;
    for (auto vecin : L[nod])
        if (!viz[vecin])
            dfs (vecin);
}
void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].minia = a[v[st]];
        aint[nod].maxib = b[v[st]];
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod].minia = min (aint[nod<<1].minia,aint[(nod<<1)|1].minia);
    aint[nod].maxib = max (aint[nod<<1].maxib,aint[(nod<<1)|1].maxib);
}
void query (int nod, int st, int dr, int x, int y){

    if (x <= st && dr <= y){
        mini = min (mini,aint[nod].minia);
        maxi = max (maxi,aint[nod].maxib);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query(nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}
int solve (int v[], int k){
    for (i=1;i<=4*k;i++){
        poz[i].clear();
        aint[i] = {0,0};
    }

    for (i=1;i<=k;i++)
        poz[a[v[i]]].push_back(i);


    build (1,1,k);

    int ok = 1;

    for (i=1;i<=k;i++){
        if (a[v[i]] == b[v[i]])
            continue;

        int lft = 0, rgh = 0;
        for (auto it : poz[b[v[i]]]){
            if (it < i)
                lft = it;
            if (it > i){
                rgh = it;
                break;
            }
        }

        int ok2 = 0;
        if (lft){
            mini = INF, maxi = -INF;
            query (1,1,k,lft,i-1);
            if (mini >= b[v[i]] && maxi <= b[v[i]])
                ok2 = 1;
        }
        if (rgh){
            mini = INF, maxi = -INF;
            query (1,1,k,i+1,rgh);
            if (mini >= b[v[i]] && maxi <= b[v[i]])
                ok2 = 1;
        }

        if (!ok2){
            ok = 0;
            break;
        }
    }

    return ok;
}

void dfs2 (int nod){
    viz[nod] = 1;
    if (nod != i && a[nod] == b[i])
        g = 1;
    for (auto vecin : L[nod])
        if (!viz[vecin])
            if (a[vecin] >= b[i] && b[vecin] <= b[i])
                dfs2 (vecin);
}
int main (){

  //  ifstream cin ("colors2.in");
   // ofstream cout ("colors2.out");

    cin>>t;
    for (int q=1;q<=t;q++){
        if (q == 36)
            q = 36;
        cin>>n>>m;

        for (i=1;i<=n;i++){
            L[i].clear();
            f[i] = 0;
        }

        for (i=1;i<=n;i++){
            cin>>a[i];
            f[a[i]]++;
        }

        int ok = 1;
        for (i=1;i<=n;i++){
            cin>>b[i];
            if (b[i] > a[i] || !f[b[i]])
                ok = 0;
        }
        for (i=1;i<=m;i++){
            cin>>x>>y;
            L[x].push_back(y);
            L[y].push_back(x);
        }

        if (!ok){
            cout<<0<<"\n";
            continue;
        }

        if (n == 1 && !m){
            if (a[1] == b[1])
                cout<<"1\n";
            else cout<<"0\n";
            continue;
        }

        if (n == 2 && m == 1){
            if ( (a[1] == b[1] && a[2] == b[2]) || (min (a[1],a[2]) == b[1] && min (a[1],a[2]) == b[2]) )
                cout<<"1\n";
            else cout<<"0\n";
            continue;
        }

        /// graf stea
        int nod = 0, cnt = 0;
        for (i=1;i<=n;i++){
            if (L[i].size() == 1)
                cnt++;
            else nod = i;
        }
        if (cnt == n-1){

            int maxi = 0, mini = n+1;
            for (i=1;i<=n;i++){
                if (b[i] == a[i])
                    continue;

                maxi = max (maxi,b[i]);
                if (i != nod)
                    mini = min (mini,b[i]);
            }
            if (maxi && (maxi > a[nod] || mini < b[nod])){
                cout<<"0\n";
                continue;
            }
            /// acum sa vad daca exista b[nod]
            int ok = 0;
            if (!maxi)
                ok = 1;
            for (i=1;i<=n;i++)
                if (i != nod && b[i] == b[nod]){
                    ok = 1;
                    break;
                }
            cout<<ok<<"\n";

            continue;
        }

        /// graf complet
        if (m == 1LL*n*(n-1)/2){

            cout<<1<<"\n";
            continue;
        }

        /// lant
        int start = 0;
        cnt = 0;
        for (i=1;i<=n;i++)
            if (L[i].size() == 1){
                if (!start)
                    start = i;
                cnt++;
            }

        if (cnt == 2){
            memset (viz,0,sizeof viz); k = 0;
            dfs (start);

            if (solve (v,k))
                cout<<"1\n";
            else cout<<"0\n";

            continue;
        }

        /// arbore

        for (i=1;i<=n;i++){
            if (a[i] == b[i])
                continue;
            memset (viz,0,sizeof viz);
            g = 0;
            dfs2 (i);
            if (!g)
                break;
        }
        if (i > n)
            cout<<"1\n";
        else cout<<"0\n";
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 18048 KB Output is correct
2 Correct 68 ms 18048 KB Output is correct
3 Correct 20 ms 18048 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 18048 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 18560 KB Output is correct
2 Correct 83 ms 18688 KB Output is correct
3 Correct 22 ms 18720 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 18560 KB Output is correct
2 Correct 83 ms 18688 KB Output is correct
3 Correct 22 ms 18720 KB Output is correct
4 Correct 472 ms 18680 KB Output is correct
5 Correct 605 ms 25568 KB Output is correct
6 Correct 757 ms 39612 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 18048 KB Output is correct
2 Correct 68 ms 18048 KB Output is correct
3 Correct 20 ms 18048 KB Output is correct
4 Correct 278 ms 18560 KB Output is correct
5 Correct 83 ms 18688 KB Output is correct
6 Correct 22 ms 18720 KB Output is correct
7 Correct 1372 ms 18696 KB Output is correct
8 Correct 497 ms 19192 KB Output is correct
9 Correct 130 ms 18688 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2800 ms 18896 KB Output is correct
2 Execution timed out 3077 ms 20728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 18560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 18048 KB Output is correct
2 Correct 68 ms 18048 KB Output is correct
3 Correct 20 ms 18048 KB Output is correct
4 Correct 179 ms 18048 KB Output is correct
5 Correct 278 ms 18560 KB Output is correct
6 Correct 83 ms 18688 KB Output is correct
7 Correct 22 ms 18720 KB Output is correct
8 Correct 472 ms 18680 KB Output is correct
9 Correct 605 ms 25568 KB Output is correct
10 Correct 757 ms 39612 KB Output is correct
11 Correct 1372 ms 18696 KB Output is correct
12 Correct 497 ms 19192 KB Output is correct
13 Correct 130 ms 18688 KB Output is correct
14 Correct 2800 ms 18896 KB Output is correct
15 Execution timed out 3077 ms 20728 KB Time limit exceeded
16 Halted 0 ms 0 KB -