제출 #225517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
225517		nicolaalexandra	Colors (RMI18_colors)	C++14	78 / 100	3065 ms	64480 KiB

colors

#include <bits/stdc++.h>
#define DIM 150010
#define DIMBUFF 10000000
#define INF 2000000000
using namespace std;
vector <int> poz_a[DIM],poz_b[DIM];
int a[DIM],b[DIM],f[DIM],f2[DIM],c[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,pos;

char buff[DIMBUFF];
vector <pair<int,int> > aint2[DIM*4];
pair<int,int> s[DIM];


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 (int i=0;i<aint2[nod].size();++i){

        int radx = get_rad (aint2[nod][i].first), rady = get_rad (aint2[nod][i].second);
        unite (radx,rady);
    }

    if (st == dr){ /// acum trb sa fac query ul
        /// marchez culorile de a
        for (int i=0;i<poz_a[st].size();++i){
            int x = get_rad(poz_a[st][i]);
            mrk[x] = st;
        }

        for (int i=0;i<poz_b[st].size();++i){
            int x = get_rad(poz_b[st][i]);
            if (mrk[x] != 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
    while (u > size_init)
        undo();
}
int get_nr(){
    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr*10 + buff[pos] - '0';
        pos++;
    }
    return nr;
}
int main (){

  //  FILE *fin = fopen ("colors2.in","r");
 //   FILE *fout = fopen ("colors2.out","w");
    FILE *fin = stdin;
    FILE *fout = stdout;

    fread (buff,1,DIMBUFF,fin);

    t = get_nr();
    for (int q=1;q<=t;++q){
        //if (q == 36)
          //  q = 36;
        //cin>>n>>m;
        n = get_nr(), m = get_nr();

        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];
            a[i] = get_nr();
            ++f[a[i]];
            poz_a[a[i]].push_back(i);
        }

        int ok = 1;
        for (i=1;i<=n;++i){
            //cin>>b[i];
            b[i] = get_nr();
            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;
            x = get_nr(), y = get_nr();
            /// fac update in aint cu intervalul pt muchia asta
            int mini = min (a[x],a[y]);
            int maxi = max (b[x],b[y]);
            update_aint (1,1,n,maxi,mini,x,y);

        }

        if (!ok){
            //cout<<0<<"\n";
            fprintf(fout,"0\n");
            continue;
        }

        if (n == 1 && !m){
            if (a[1] == b[1])
                fprintf(fout,"1\n");
            else fprintf(fout,"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]) )
                fprintf(fout,"1\n");
            else fprintf(fout,"0\n");
            continue;
        }

        /// de aici devine interesant

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

        fprintf(fout,"%d\n",sol_final);
        //cout<<sol_final<<"\n";
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

colors.cpp: In function 'void unite(int, int)':
colors.cpp:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (Size[radx] < Size[rady]);
     ^~
colors.cpp:39:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         swap (radx,rady);
         ^~~~
colors.cpp: In function 'void query_aint(int, int, int)':
colors.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<aint2[nod].size();++i){
                  ~^~~~~~~~~~~~~~~~~~
colors.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<poz_a[st].size();++i){
                      ~^~~~~~~~~~~~~~~~~
colors.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<poz_b[st].size();++i){
                      ~^~~~~~~~~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:112:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff,1,DIMBUFF,fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

• 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: 0 / 22