제출 #225359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
225359		nicolaalexandra	Colors (RMI18_colors)	C++14	22 / 100	525 ms	21716 KiB

colors

#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;
struct seg_tree{
    int mini,lazy;
} 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].mini = a[v[st]];
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod].mini = min (aint[nod<<1].mini,aint[(nod<<1)|1].mini);
}
void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;
    if (st != dr){
        aint[nod<<1].mini = aint[nod<<1].lazy = aint[nod].lazy;
        aint[(nod<<1)|1].mini = aint[(nod<<1)|1].lazy = aint[nod].lazy;
    }
    aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].mini = val;
        aint[nod].lazy = val;
        update_lazy (nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);

    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    aint[nod].mini = min (aint[nod<<1].mini,aint[(nod<<1)|1].mini);
}
void query (int nod, int st, int dr, int x, int y){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        sol = min (sol,aint[nod].mini);
        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 get_elem (int nod, int st, int dr, int poz){
    update_lazy (nod,st,dr);
    if (st == dr)
        return aint[nod].mini;
    int mid = (st+dr)>>1;
    if (poz <= mid)
        return get_elem (nod<<1,st,mid,poz);
    else return get_elem ((nod<<1)|1,mid+1,dr,poz);
}
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 (get_elem (1,1,k,i) == b[v[i]])
            continue;
        /// caut b[v[i]];
        int x = v[i], p = 0;
        if (i > 1 && get_elem (1,1,k,i-1) == b[x]){
            update (1,1,k,i,i,b[x]);
            continue;
        }


        for (auto it : poz[b[x]]){
            if (it <= i)
                continue;
            if (get_elem (1,1,k,it) == b[x]){
                p = it;
                break;
            }}

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

        /// minimul din interval
        sol = INF;
        query (1,1,k,i,p);
        if (sol < b[x]){
            ok = 0;
            break;
        }

        update (1,1,k,i,p,b[x]);

    }
    return ok;
}
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;
        for (i=1;i<=n;i++)
            if (L[i].size() == 1){
                start = i;
                break;
            }
        memset (viz,0,sizeof viz); k = 0;
        dfs (start);

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

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

    }

    return 0;
}

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