oj.uz

Submission #225397

# Submission time Handle Problem Language Result Execution time Memory
225397 2020-04-20T13:24:49 Z nicolaalexandra Colors (RMI18_colors) C++14
62 / 100
 3000 ms 46300 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 && m == n-1){
            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 162 ms 19448 KB Output is correct
2 Correct 71 ms 18552 KB Output is correct
3 Correct 19 ms 18176 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 19704 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 20064 KB Output is correct
2 Correct 80 ms 19068 KB Output is correct
3 Correct 21 ms 18816 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 20064 KB Output is correct
2 Correct 80 ms 19068 KB Output is correct
3 Correct 21 ms 18816 KB Output is correct
4 Correct 466 ms 21728 KB Output is correct
5 Correct 579 ms 31736 KB Output is correct
6 Correct 697 ms 46300 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 19448 KB Output is correct
2 Correct 71 ms 18552 KB Output is correct
3 Correct 19 ms 18176 KB Output is correct
4 Correct 289 ms 20064 KB Output is correct
5 Correct 80 ms 19068 KB Output is correct
6 Correct 21 ms 18816 KB Output is correct
7 Correct 1341 ms 20088 KB Output is correct
8 Correct 481 ms 19192 KB Output is correct
9 Correct 141 ms 18688 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2745 ms 21728 KB Output is correct
2 Execution timed out 3095 ms 20856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 19320 KB Output is correct
2 Correct 100 ms 19040 KB Output is correct
3 Correct 122 ms 18688 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 19448 KB Output is correct
2 Correct 71 ms 18552 KB Output is correct
3 Correct 19 ms 18176 KB Output is correct
4 Correct 176 ms 19704 KB Output is correct
5 Correct 289 ms 20064 KB Output is correct
6 Correct 80 ms 19068 KB Output is correct
7 Correct 21 ms 18816 KB Output is correct
8 Correct 466 ms 21728 KB Output is correct
9 Correct 579 ms 31736 KB Output is correct
10 Correct 697 ms 46300 KB Output is correct
11 Correct 1341 ms 20088 KB Output is correct
12 Correct 481 ms 19192 KB Output is correct
13 Correct 141 ms 18688 KB Output is correct
14 Correct 2745 ms 21728 KB Output is correct
15 Execution timed out 3095 ms 20856 KB Time limit exceeded
16 Halted 0 ms 0 KB -