oj.uz

Submission #225517

# Submission time Handle Problem Language Result Execution time Memory
225517 2020-04-20T17:38:16 Z nicolaalexandra Colors (RMI18_colors) C++14
78 / 100
 3000 ms 64480 KB 
#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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23040 KB Output is correct
2 Correct 35 ms 22144 KB Output is correct
3 Correct 32 ms 21888 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 23416 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 23040 KB Output is correct
2 Correct 28 ms 22144 KB Output is correct
3 Correct 18 ms 21888 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 23040 KB Output is correct
2 Correct 28 ms 22144 KB Output is correct
3 Correct 18 ms 21888 KB Output is correct
4 Correct 83 ms 24704 KB Output is correct
5 Correct 320 ms 43744 KB Output is correct
6 Correct 588 ms 64480 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23040 KB Output is correct
2 Correct 35 ms 22144 KB Output is correct
3 Correct 32 ms 21888 KB Output is correct
4 Correct 47 ms 23040 KB Output is correct
5 Correct 28 ms 22144 KB Output is correct
6 Correct 18 ms 21888 KB Output is correct
7 Correct 50 ms 23040 KB Output is correct
8 Correct 34 ms 22192 KB Output is correct
9 Correct 22 ms 21888 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 24704 KB Output is correct
2 Correct 1068 ms 44460 KB Output is correct
3 Correct 2095 ms 55836 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 22400 KB Output is correct
2 Correct 28 ms 22144 KB Output is correct
3 Correct 24 ms 21760 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23040 KB Output is correct
2 Correct 35 ms 22144 KB Output is correct
3 Correct 32 ms 21888 KB Output is correct
4 Correct 61 ms 23416 KB Output is correct
5 Correct 47 ms 23040 KB Output is correct
6 Correct 28 ms 22144 KB Output is correct
7 Correct 18 ms 21888 KB Output is correct
8 Correct 83 ms 24704 KB Output is correct
9 Correct 320 ms 43744 KB Output is correct
10 Correct 588 ms 64480 KB Output is correct
11 Correct 50 ms 23040 KB Output is correct
12 Correct 34 ms 22192 KB Output is correct
13 Correct 22 ms 21888 KB Output is correct
14 Correct 83 ms 24704 KB Output is correct
15 Correct 1068 ms 44460 KB Output is correct
16 Correct 2095 ms 55836 KB Output is correct
17 Correct 38 ms 22400 KB Output is correct
18 Correct 28 ms 22144 KB Output is correct
19 Correct 24 ms 21760 KB Output is correct
20 Correct 82 ms 24184 KB Output is correct
21 Execution timed out 3065 ms 34336 KB Time limit exceeded
22 Halted 0 ms 0 KB -