oj.uz

Submission #225406

# Submission time Handle Problem Language Result Execution time Memory
225406 2020-04-20T13:52:21 Z nicolaalexandra Colors (RMI18_colors) C++14
78 / 100
 2744 ms 514828 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],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;
                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 167 ms 19448 KB Output is correct
2 Correct 72 ms 18552 KB Output is correct
3 Correct 21 ms 18048 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 20088 KB Output is correct
2 Correct 79 ms 19064 KB Output is correct
3 Correct 27 ms 18816 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 20088 KB Output is correct
2 Correct 79 ms 19064 KB Output is correct
3 Correct 27 ms 18816 KB Output is correct
4 Correct 486 ms 20780 KB Output is correct
5 Correct 589 ms 27512 KB Output is correct
6 Correct 705 ms 41720 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 19448 KB Output is correct
2 Correct 72 ms 18552 KB Output is correct
3 Correct 21 ms 18048 KB Output is correct
4 Correct 272 ms 20088 KB Output is correct
5 Correct 79 ms 19064 KB Output is correct
6 Correct 27 ms 18816 KB Output is correct
7 Correct 1471 ms 20192 KB Output is correct
8 Correct 512 ms 19152 KB Output is correct
9 Correct 135 ms 18688 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2744 ms 20856 KB Output is correct
2 Correct 629 ms 55800 KB Output is correct
3 Correct 776 ms 132344 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 19448 KB Output is correct
2 Correct 104 ms 18936 KB Output is correct
3 Correct 125 ms 18688 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 19448 KB Output is correct
2 Correct 72 ms 18552 KB Output is correct
3 Correct 21 ms 18048 KB Output is correct
4 Correct 172 ms 19704 KB Output is correct
5 Correct 272 ms 20088 KB Output is correct
6 Correct 79 ms 19064 KB Output is correct
7 Correct 27 ms 18816 KB Output is correct
8 Correct 486 ms 20780 KB Output is correct
9 Correct 589 ms 27512 KB Output is correct
10 Correct 705 ms 41720 KB Output is correct
11 Correct 1471 ms 20192 KB Output is correct
12 Correct 512 ms 19152 KB Output is correct
13 Correct 135 ms 18688 KB Output is correct
14 Correct 2744 ms 20856 KB Output is correct
15 Correct 629 ms 55800 KB Output is correct
16 Correct 776 ms 132344 KB Output is correct
17 Correct 273 ms 19448 KB Output is correct
18 Correct 104 ms 18936 KB Output is correct
19 Correct 125 ms 18688 KB Output is correct
20 Correct 672 ms 20984 KB Output is correct
21 Runtime error 539 ms 514828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -