oj.uz

Submission #225410

# Submission time Handle Problem Language Result Execution time Memory
225410 2020-04-20T13:58:01 Z nicolaalexandra Colors (RMI18_colors) C++14
78 / 100
 796 ms 524288 KB 
#include <bits/stdc++.h>
#define DIM 300010
#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],E[DIM*4],first[DIM],level[DIM],p[DIM*4],idx[DIM];
int t,n,m,i,j,x,y,k,sol,mini,maxi,ok,g;
struct seg_tree{
    int minia,maxib;
} aint[4*DIM];
struct idk{
    int nod, minia, maxib;
} dp[DIM][30];
pair <int,int> rmq[30][DIM*4];

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);
}

void dfs3 (int nod, int tata){
    dp[nod][0] = {tata, a[nod],b[nod]};
    E[++k] = nod;
    first[nod] = k;
    level[nod] = 1 + level[tata];
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs3 (vecin,nod);
            E[++k] = nod;
        }
}

int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy - posx + 1];
    pair <int, int> sol = min (rmq[nr][posx], rmq[nr][posy - (1<<nr) + 1]);
    return E[sol.second];
}

void solve2 (int x, int y){

    int lca = get_lca (x,y);
    for (int i=20;i>=0;i--){
        if (dp[x][i].nod && level[dp[x][i].nod] >= level[lca]){
            mini = min (mini,dp[x][i].minia);
            maxi = max (maxi,dp[x][i].maxib);
            x = dp[x][i].nod;
        }
    }

    for (int i=20;i>=0;i--){
        if (dp[y][i].nod && level[dp[y][i].nod] >= level[lca]){
            mini = min (mini,dp[y][i].minia);
            maxi = max (maxi,dp[y][i].maxib);
            x = dp[y][i].nod;
        }
    }

}

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

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

            continue;
        }

        /// permutarea
        k = 0;
        dfs3 (1,0);

        for (i=1;i<=k;i++)
            rmq[0][i] = make_pair(level[E[i]],i);

        for (i=1;(1<<i)<=k;i++)
            for (j=1;j<=k;j++){
                rmq[i][j] = rmq[i-1][j];
                if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                    rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
            }

        for (i=2;i<=k;i++)
            p[i] = p[i/2] + 1;


        for (j=1;(1<<j)<=n;j++)
            for (i=1;i<=n;i++){
                dp[i][j].nod = dp[dp[i][j-1].nod][j-1].nod;
                dp[i][j].minia = min (dp[i][j-1].minia, dp[ dp[i][j-1].nod ][j-1].minia);
                dp[i][j].maxib = max (dp[i][j-1].maxib, dp[ dp[i][j-1].nod ][j-1].maxib);
            }

        for (i=1;i<=n;i++)
            idx[a[i]] = i;

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

            mini = INF, maxi = -INF;
            solve2 (idx[b[i]],i);

            if (mini < b[i] || maxi > b[i])
                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 183 ms 35644 KB Output is correct
2 Correct 76 ms 35704 KB Output is correct
3 Correct 29 ms 35584 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 35584 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 36948 KB Output is correct
2 Correct 96 ms 36736 KB Output is correct
3 Correct 31 ms 36864 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 36948 KB Output is correct
2 Correct 96 ms 36736 KB Output is correct
3 Correct 31 ms 36864 KB Output is correct
4 Correct 602 ms 36856 KB Output is correct
5 Correct 577 ms 43768 KB Output is correct
6 Correct 699 ms 57724 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 35644 KB Output is correct
2 Correct 76 ms 35704 KB Output is correct
3 Correct 29 ms 35584 KB Output is correct
4 Correct 401 ms 36948 KB Output is correct
5 Correct 96 ms 36736 KB Output is correct
6 Correct 31 ms 36864 KB Output is correct
7 Correct 212 ms 36736 KB Output is correct
8 Correct 97 ms 36864 KB Output is correct
9 Correct 77 ms 35584 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 37876 KB Output is correct
2 Correct 642 ms 76312 KB Output is correct
3 Correct 796 ms 146296 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 36728 KB Output is correct
2 Correct 63 ms 35712 KB Output is correct
3 Correct 73 ms 35704 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 35644 KB Output is correct
2 Correct 76 ms 35704 KB Output is correct
3 Correct 29 ms 35584 KB Output is correct
4 Correct 180 ms 35584 KB Output is correct
5 Correct 401 ms 36948 KB Output is correct
6 Correct 96 ms 36736 KB Output is correct
7 Correct 31 ms 36864 KB Output is correct
8 Correct 602 ms 36856 KB Output is correct
9 Correct 577 ms 43768 KB Output is correct
10 Correct 699 ms 57724 KB Output is correct
11 Correct 212 ms 36736 KB Output is correct
12 Correct 97 ms 36864 KB Output is correct
13 Correct 77 ms 35584 KB Output is correct
14 Correct 422 ms 37876 KB Output is correct
15 Correct 642 ms 76312 KB Output is correct
16 Correct 796 ms 146296 KB Output is correct
17 Correct 113 ms 36728 KB Output is correct
18 Correct 63 ms 35712 KB Output is correct
19 Correct 73 ms 35704 KB Output is correct
20 Correct 300 ms 38008 KB Output is correct
21 Runtime error 654 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -