oj.uz

Submission #225514

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

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

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

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

    return 0;
}

Compilation message

colors.cpp: In function 'void unite(int, int)':
colors.cpp:43:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (Size[radx] < Size[rady]);
     ^~
colors.cpp:44: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:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<poz_a[st].size();i++){
                      ~^~~~~~~~~~~~~~~~~
colors.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<poz_b[st].size();i++){
                      ~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 78840 KB Output is correct
2 Correct 109 ms 78328 KB Output is correct
3 Correct 64 ms 78328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 79136 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 78968 KB Output is correct
2 Correct 102 ms 78456 KB Output is correct
3 Correct 51 ms 78200 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 78968 KB Output is correct
2 Correct 102 ms 78456 KB Output is correct
3 Correct 51 ms 78200 KB Output is correct
4 Correct 405 ms 79224 KB Output is correct
5 Correct 774 ms 95056 KB Output is correct
6 Correct 1033 ms 115156 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 78840 KB Output is correct
2 Correct 109 ms 78328 KB Output is correct
3 Correct 64 ms 78328 KB Output is correct
4 Correct 218 ms 78968 KB Output is correct
5 Correct 102 ms 78456 KB Output is correct
6 Correct 51 ms 78200 KB Output is correct
7 Correct 219 ms 79224 KB Output is correct
8 Correct 107 ms 78456 KB Output is correct
9 Correct 59 ms 78328 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 78840 KB Output is correct
2 Correct 1501 ms 95976 KB Output is correct
3 Execution timed out 3085 ms 103780 KB Time limit exceeded

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 78712 KB Output is correct
2 Correct 77 ms 78584 KB Output is correct
3 Correct 63 ms 78204 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 78840 KB Output is correct
2 Correct 109 ms 78328 KB Output is correct
3 Correct 64 ms 78328 KB Output is correct
4 Correct 235 ms 79136 KB Output is correct
5 Correct 218 ms 78968 KB Output is correct
6 Correct 102 ms 78456 KB Output is correct
7 Correct 51 ms 78200 KB Output is correct
8 Correct 405 ms 79224 KB Output is correct
9 Correct 774 ms 95056 KB Output is correct
10 Correct 1033 ms 115156 KB Output is correct
11 Correct 219 ms 79224 KB Output is correct
12 Correct 107 ms 78456 KB Output is correct
13 Correct 59 ms 78328 KB Output is correct
14 Correct 399 ms 78840 KB Output is correct
15 Correct 1501 ms 95976 KB Output is correct
16 Execution timed out 3085 ms 103780 KB Time limit exceeded