oj.uz

Submission #225516

# Submission time Handle Problem Language Result Execution time Memory
225516 2020-04-20T17:31:10 Z nicolaalexandra Colors (RMI18_colors) C++14
78 / 100
 3000 ms 69208 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 (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 (int i=0;i<poz_a[st].size();++i){
            int x = poz_a[st][i];
            mrk[get_rad(x)] = st;
        }

        for (int i=0;i<poz_b[st].size();++i){
            int x = poz_b[st][i];
            if (mrk[get_rad(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
            update_aint (1,1,n,max(b[x],b[y]),min(a[x],a[y]),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:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<poz_a[st].size();++i){
                      ~^~~~~~~~~~~~~~~~~
colors.cpp:77: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:111: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 24448 KB Output is correct
2 Correct 35 ms 22656 KB Output is correct
3 Correct 33 ms 22008 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 25080 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 24576 KB Output is correct
2 Correct 29 ms 22656 KB Output is correct
3 Correct 19 ms 21888 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 24576 KB Output is correct
2 Correct 29 ms 22656 KB Output is correct
3 Correct 19 ms 21888 KB Output is correct
4 Correct 80 ms 27776 KB Output is correct
5 Correct 301 ms 48340 KB Output is correct
6 Correct 562 ms 69208 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 24448 KB Output is correct
2 Correct 35 ms 22656 KB Output is correct
3 Correct 33 ms 22008 KB Output is correct
4 Correct 46 ms 24576 KB Output is correct
5 Correct 29 ms 22656 KB Output is correct
6 Correct 19 ms 21888 KB Output is correct
7 Correct 47 ms 23040 KB Output is correct
8 Correct 30 ms 22144 KB Output is correct
9 Correct 28 ms 21888 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 24708 KB Output is correct
2 Correct 1035 ms 44484 KB Output is correct
3 Correct 2076 ms 59620 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 27 ms 22144 KB Output is correct
3 Correct 25 ms 21760 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 24448 KB Output is correct
2 Correct 35 ms 22656 KB Output is correct
3 Correct 33 ms 22008 KB Output is correct
4 Correct 59 ms 25080 KB Output is correct
5 Correct 46 ms 24576 KB Output is correct
6 Correct 29 ms 22656 KB Output is correct
7 Correct 19 ms 21888 KB Output is correct
8 Correct 80 ms 27776 KB Output is correct
9 Correct 301 ms 48340 KB Output is correct
10 Correct 562 ms 69208 KB Output is correct
11 Correct 47 ms 23040 KB Output is correct
12 Correct 30 ms 22144 KB Output is correct
13 Correct 28 ms 21888 KB Output is correct
14 Correct 81 ms 24708 KB Output is correct
15 Correct 1035 ms 44484 KB Output is correct
16 Correct 2076 ms 59620 KB Output is correct
17 Correct 38 ms 22400 KB Output is correct
18 Correct 27 ms 22144 KB Output is correct
19 Correct 25 ms 21760 KB Output is correct
20 Correct 98 ms 26616 KB Output is correct
21 Execution timed out 3073 ms 40284 KB Time limit exceeded
22 Halted 0 ms 0 KB -