oj.uz

Submission #209602

# Submission time Handle Problem Language Result Execution time Memory
209602 2020-03-14T19:13:40 Z nicolaalexandra Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 373 ms 67448 KB 
#include <bits/stdc++.h>
#define DIM 500010
using namespace std;
int level[DIM],fth[DIM],Left[DIM],Right[DIM];
int E[DIM*4],p[DIM*4],first[DIM],viz[DIM],tata[DIM],dp_min[DIM],dp_max[DIM];
pair <int,int> rmq[30][DIM];
vector <int> L[DIM],edg[DIM];
struct _update{
    int tip,x,y,val;
};
_update v[DIM],w[DIM];
map <int,int> poz;
int n,m,i,j,x,y,val,dist,lca,k,tip,el,ok,idx;
char ch;

void dfs (int nod, int father){
    E[++k] = nod;
    first[nod] = k;
    level[nod] = 1 + level[father];
    fth[nod] = tata[nod] = father;
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (vecin != father){
            dfs (vecin,nod);
            E[++k] = nod;
        }}}

int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy-posx+1];
    pair <int,int> sol = min (rmq[nr][posx],rmq[nr][posy-(1<<nr)+1]);
    return E[sol.second];
}

inline int cmp (_update a, _update b){
    return a.val < b.val;
}

int cupleaza (int nod){
    if (viz[nod])
        return 0;

    viz[nod] = 1;
    for (auto vecin : edg[nod]){
        if (Right[vecin] == 0){
            Left[nod] = vecin;
            Right[vecin] = nod;
            return 1;
        } }

    for (auto vecin : edg[nod]){
        if (cupleaza(Right[vecin])){
            Left[nod] = vecin;
            Right[vecin] = nod;
            return 1;
        }}

    return 0;
}

int main (){

   // ifstream cin ("minmaxtree.in");
   // ofstream cout ("minmaxtree.out");

    cin>>n;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    dfs (1,0);

    for (i=1;i<=k;i++)
        rmq[0][i] = make_pair (level[E[i]],i);

    for (i=1;(1<<i)<=k;i++){
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }}

    for (i=2;i<=k;i++)
        p[i] = p[i/2] + 1;

    cin>>m;
    for (i=1;i<=m;i++){
        cin>>ch>>x>>y>>val;
        if (ch == 'M')
            tip = 1;
        else tip = 0;

        v[i] =  {tip,x,y,val};

        poz[val] = i;

        if (tip)
            w[++el] = v[i];
    }

    /// dp_min[nod] - minimul valorilor de maxim care trec prin muchia nod-fth[nod]

    sort (w+1,w+el+1,cmp);
    for (i=1;i<=el;i++){
        int x = w[i].x, y = w[i].y, val = w[i].val;
        lca = get_lca (x,y);

        /// acum incerc sa fac toate valorile nemcacate de pe drumul de la x la lca egale cu val
        int nod = x;
        while (nod && level[nod] > level[lca]){

            if (!dp_min[nod])
                dp_min[nod] = val;

            int aux = nod;
            nod = fth[nod];
            fth[aux] = lca;
        }


        nod = y;
        while (nod && level[nod] > level[lca]){

            if (!dp_min[nod])
                dp_min[nod] = val;

            int aux = nod;
            nod = fth[nod];
            fth[aux] = lca;
        }
    }


    for (i=1;i<=n;i++)
        fth[i] = tata[i];

    /// acum facem dp_max pentru minime

    el = 0;
    for (i=1;i<=n;i++){
        if (v[i].tip == 0)
            w[++el] = v[i];
    }
    sort (w+1,w+el+1,cmp);

    for (i=el;i;i--){
        int x = w[i].x, y = w[i].y, val = w[i].val;
        lca = get_lca (x,y);

        /// acum incerc sa fac toate valorile nemcacate de pe drumul de la x la lca egale cu val
        int nod = x;
        while (nod && level[nod] > level[lca]){

            if (!dp_max[nod])
                dp_max[nod] = val;


            int aux = nod;
            nod = fth[nod];
            fth[aux] = lca;
        }


        nod = y;
        while (nod && level[nod] > level[lca]){

            if (!dp_max[nod])
                dp_max[nod] = val;

            int aux = nod;
            nod = fth[nod];
            fth[aux] = lca;
        }

    }

    /// acum trb sa stabilesc pt fiecare nod daca sa aleg dp_max sau dp_min
    /// si fiecare valoare din input trb sa apara cel putin odata

    for (i=1;i<=n;i++){
        if (dp_max[i]){
            idx = poz[dp_max[i]];

            edg[i].push_back (n + idx);
            edg[n + idx].push_back (i);
        }

        if (dp_min[i]){
            idx = poz[dp_min[i]];

            edg[i].push_back(n + idx);
            edg[n + idx].push_back(i);
        }

    }


    do{
        memset (viz,0,sizeof viz);
        ok = 0;
        for (i=1;i<=n;i++){
            if (!Left[i] && cupleaza(i))
                ok = 1;
        }
    } while (ok);

    //for (i=2;i<=n;i++)
      //  cout<<dp_max[i]<<" "<<dp_min[i]<<endl;

    for (i=2;i<=n;i++){
        cout<<i<<" "<<tata[i]<<" ";
        int idx = Left[i];
        if (idx)
            cout<<v[idx - n].val<<"\n";
        else cout<<max(dp_min[i],dp_max[i])<<"\n";
    }



    return 0;
}

Compilation message

minmaxtree.cpp: In function 'void dfs(int, int)':
minmaxtree.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<L[nod].size();i++){
                  ~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25720 KB Output is correct
2 Correct 20 ms 25848 KB Output is correct
3 Correct 21 ms 25848 KB Output is correct
4 Correct 20 ms 25848 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 64120 KB Output is correct
2 Correct 316 ms 61432 KB Output is correct
3 Correct 287 ms 61688 KB Output is correct
4 Correct 327 ms 64632 KB Output is correct
5 Correct 301 ms 61816 KB Output is correct
6 Correct 362 ms 62456 KB Output is correct
7 Correct 313 ms 61560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 56696 KB Output is correct
2 Correct 209 ms 58360 KB Output is correct
3 Correct 200 ms 59128 KB Output is correct
4 Correct 194 ms 60024 KB Output is correct
5 Correct 217 ms 59000 KB Output is correct
6 Correct 224 ms 59768 KB Output is correct
7 Correct 225 ms 59128 KB Output is correct
8 Correct 220 ms 59000 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25720 KB Output is correct
2 Correct 20 ms 25848 KB Output is correct
3 Correct 21 ms 25848 KB Output is correct
4 Correct 20 ms 25848 KB Output is correct
5 Correct 328 ms 64120 KB Output is correct
6 Correct 316 ms 61432 KB Output is correct
7 Correct 287 ms 61688 KB Output is correct
8 Correct 327 ms 64632 KB Output is correct
9 Correct 301 ms 61816 KB Output is correct
10 Correct 362 ms 62456 KB Output is correct
11 Correct 313 ms 61560 KB Output is correct
12 Correct 207 ms 56696 KB Output is correct
13 Correct 209 ms 58360 KB Output is correct
14 Correct 200 ms 59128 KB Output is correct
15 Correct 194 ms 60024 KB Output is correct
16 Correct 217 ms 59000 KB Output is correct
17 Correct 224 ms 59768 KB Output is correct
18 Correct 225 ms 59128 KB Output is correct
19 Correct 220 ms 59000 KB Output is correct
20 Correct 336 ms 63864 KB Output is correct
21 Correct 295 ms 61944 KB Output is correct
22 Correct 285 ms 62200 KB Output is correct
23 Correct 292 ms 62584 KB Output is correct
24 Correct 373 ms 66296 KB Output is correct
25 Correct 355 ms 67448 KB Output is correct
26 Correct 343 ms 66680 KB Output is correct
27 Correct 361 ms 65656 KB Output is correct
28 Correct 359 ms 64632 KB Output is correct
29 Correct 366 ms 64760 KB Output is correct
30 Correct 337 ms 62840 KB Output is correct
31 Correct 336 ms 63228 KB Output is correct
32 Correct 364 ms 64376 KB Output is correct
33 Correct 335 ms 63608 KB Output is correct
34 Correct 343 ms 63600 KB Output is correct
35 Correct 321 ms 62968 KB Output is correct