Submission #225519

#	Time	Username	Problem	Language	Result	Execution time	Memory
225519		nicolaalexandra	Colors (RMI18_colors)	C++14	100 / 100	1529 ms	210300 KiB

colors

#include <bits/stdc++.h>
#define DIM 300010
#define INF 2000000000
using namespace std;
vector <int> L[DIM],poz[DIM*4],poz_a[DIM],poz_b[DIM];
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 mrk[DIM],fth[DIM],Size[DIM];
int t,n,m,i,j,x,y,k,sol,mini,maxi,ok,g,sol_final,u;
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];

vector <pair<int,int> > aint2[DIM*4];
pair<int,int> s[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);
}

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

void update_aint (int nod, int st, int dr, int x, int y, int a, int b){
    if (x <= st && dr <= y){
        aint2[nod].push_back(make_pair(a,b));
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update_aint(nod<<1,st,mid,x,y,a,b);
    if (y > mid)
        update_aint ((nod<<1)|1,mid+1,dr,x,y,a,b);
}

int get_rad (int x){
    while (x != fth[x])
        x = fth[x];
    return x;
}

void unite (int radx, int rady){
    if (radx == rady)
        return;

    if (Size[radx] < Size[rady])
        swap (radx,rady);

    /// tin minte o stiva cu update urile pe care le fac ca sa pot sa fac undo
    s[++u] = make_pair(radx,rady);

    Size[radx] += Size[rady];
    fth[rady] = radx;

}

void undo (){

    int x = s[u].first, y = s[u].second;
    u--;
    Size[x] -= Size[y];
    fth[y] = y;

}

void query_aint (int nod, int st, int dr){
    /// am intrat prima oara in nod, trb sa adaug muchiile
    if (!sol_final)
        return;

    int size_init = u; /// ca sa stiu dupa cate undo uri trb sa fac

    for (auto it : aint2[nod]){
        int radx = get_rad (it.first), rady = get_rad (it.second);
        unite (radx,rady);
    }

    if (st == dr){ /// acum trb sa fac query ul
        /// marchez culorile de a
        for (auto it : poz_a[st])
            mrk[get_rad(it)] = st;

        for (auto it : poz_b[st])
            if (mrk[get_rad(it)] != st){
                sol_final = 0;
                break;
            }
    } else {
        int mid = (st+dr)>>1;
        query_aint(nod<<1,st,mid);
        query_aint((nod<<1)|1,mid+1,dr);
    }

    /// am terminat cu nod, trb sa dau undo
    int size_fin = u;
    for (int i=size_fin;i>size_init;--i)
        undo();
}

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();
            poz_a[i].clear();
            poz_b[i].clear();
            f[i] = mrk[i] = 0;
            Size[i] = 1;
            fth[i] = i;

        }
        for (i=1;i<=4*n;++i)
            aint2[i].clear();

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

        int ok = 1;
        for (i=1;i<=n;++i){
            cin>>b[i];
            poz_b[b[i]].push_back(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);

            /// fac update in aint cu intervalul pt muchia asta
            update_aint (1,1,n,max(b[x],b[y]),min(a[x],a[y]),x,y);

        }

        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;
                g = 0;
                dfs2 (i);
                if (!g)
                    break;
            }
            if (i > n)
                cout<<"1\n";
            else cout<<"0\n";

            continue;
        }

        /// permutarea
        if (m == n-1){
            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";

            continue;
        }


        /// de aici devine interesant

        sol_final = 1;
        //s.clear();
        u = 0;
        query_aint (1,1,n);

        cout<<sol_final<<"\n";
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22