제출 #216563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216563		Ruxandra985	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	383 ms	37884 KiB

minmaxtree

#include <bits/stdc++.h>
#define DIMN 70010
#define INF 1000000000
using namespace std;
int lnt , cnt;

int lvl[DIMN] , d[DIMN] , rmq[20][DIMN] , tt[DIMN] , l[DIMN] , up[DIMN];
int logg[DIMN] , poz[DIMN];
map <pair <int,int> , int> mp_max , mp_min;
bitset <DIMN> f;
int lft[DIMN] , r[DIMN];
vector <int> v[DIMN] , w[DIMN];
vector < pair < pair <int , int> , pair <int , int> > > aint[DIMN];
struct idk{
    int tip , x , y , val;
} op[DIMN];

pair <int,int> lca (int n , int x , int y){
    int dif , p2 , swapped = 0;
    /// aducem pe ac nivel
    if (lvl[x] < lvl[y]){
        swapped = 1;
        swap(x , y); /// x e mai jos
    }
    dif = lvl[x] - lvl[y] - 1;
    /// stramosul dif al lui x

     while (dif > 0 && x!=0){
        x=rmq[logg[dif]][x];
        dif=dif-(1<<logg[dif]);
    }
    /// acum sunt pe acelasi nivel
    if (rmq[0][x] == y){ /// y era tatal lui x
        if (!swapped)
            return make_pair(x , -1);
        else return make_pair(-1 , x);
    }
    if (dif != -1)
        x = rmq[0][x];

    for (p2 = logg[n] ; p2>=0 ; p2--){
        if (rmq[p2][x] != rmq[p2][y]){
            x = rmq[p2][x];
            y = rmq[p2][y];
        }
    }
    if (!swapped)
        return make_pair(x , y);
    else return make_pair(y , x);
}
void dfs_lant(int nod){
    int i,vecin,ok=0,maxi,fiu;
    cnt++;
    rmq[0][nod] = tt[nod];
    d[nod] = 1;
    maxi=0;
    fiu=0;
    for (i=0;i<v[nod].size();++i){
        vecin=v[nod][i];
        if (vecin != tt[nod]){
            ok=1;
            lvl[vecin] = 1 + lvl[nod];
            tt[vecin] = nod;
            dfs_lant(vecin);
            d[nod] += d[vecin];
            if (d[vecin]>maxi){
                maxi=d[vecin];
                fiu=vecin;
            }
        }
    }
    if (!ok){ /// frunza
        lnt++;
        l[nod]=lnt; /// lantul din care apartine
        w[lnt].push_back(nod);
    }else { /// unim cu poz
        w[l[fiu]].push_back(nod);
        l[nod]=l[fiu];
        for (i=0;i<v[nod].size();++i){
            vecin=v[nod][i];
            if (vecin!=tt[nod] && vecin!=fiu)
                up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
        }
    }
    v[nod].clear();
}
int cmp_subtask (idk a , idk b){
    return a.val > b.val;
}

void build (int lc , int nod , int st , int dr){
    int mid = (st + dr) / 2;

    if (st == dr){
        aint[lc][nod].first.first = INF + 1;
        aint[lc][nod].second.first = -1;
        return;
    }

    build (lc , 2 * nod , st , mid);
    build (lc , 2 * nod + 1 , mid + 1 , dr);


}

void update_lazy (int lc , int node , int st , int dr , int cod){
    if (cod == 1){
        if (aint[lc][node].first.second == 0)
            return;
        if (st == dr){
            aint[lc][node].first.second= 0;
            return;
        }

        aint[lc][2 * node].first.first = aint[lc][node].first.first;
        aint[lc][2 * node + 1].first.first = aint[lc][node].first.first;

        aint[lc][2 * node].first.second = 1;
        aint[lc][2 * node + 1].first.second = 1;

        aint[lc][node].first.second = 0;
    }
    else {
        if (aint[lc][node].second.second == 0)
            return;
        if (st == dr){
            aint[lc][node].second.second= 0;
            return;
        }

        aint[lc][2 * node].second.first = aint[lc][node].second.first;
        aint[lc][2 * node + 1].second.first = aint[lc][node].second.first;

        aint[lc][2 * node].second.second = 1;
        aint[lc][2 * node + 1].second.second = 1;

        aint[lc][node].second.second = 0;
    }

}

void update_aint (int lc , int node , int st , int dr , int l , int r , int val , int cod){
    int mid;
    update_lazy(lc , node , st , dr , cod);
    if (l <= st && dr <= r){
        if (cod == 1){
            aint[lc][node].first.first = val;
            aint[lc][node].first.second = 1; /// asta e lazy ul
        }
        else {
            aint[lc][node].second.first = val;
            aint[lc][node].second.second = 1; /// asta e lazy ul
        }
        update_lazy(lc , node , st , dr , cod);
        return;
    }
    mid=((st+dr)>>1);
    update_lazy(lc , 2 * node , st , mid , cod);
    update_lazy(lc , 2 * node + 1 , mid + 1 , dr , cod);
    if (l <= mid){
        update_aint( lc , 2 * node , st , mid , l , r , val , cod);
    }
    if (mid + 1 <= r){
        update_aint( lc , 2 * node + 1 , mid + 1 , dr , l , r , val , cod);
    }

    update_lazy(lc , 2 * node , st , mid , cod);
    update_lazy(lc , 2 * node + 1 , mid + 1 , dr , cod);



}
void update (int x , int y , int val , int cod){
    if (l[x]!=l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]]){
            update_aint (l[x] , 1 , 0 , w[l[x]].size() - 1 , 0 , poz[x] , val , cod);
            update ( up[l[x]] , y , val , cod);
        }
        else{
            update ( x , up[l[y]] , val , cod);

            update_aint( l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y] , val , cod);
        }
    }
    else {
        if (poz[x] <= poz[y])
            update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , poz[x] , poz[y] , val , cod);
        else
            update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , poz[y] , poz[x] , val , cod);
    }
}

void query (int lc , int nod , int st , int dr){
    int mid = (st + dr) / 2;

    update_lazy(lc , nod , st , dr , 1);
    update_lazy(lc , nod , st , dr , 2);

    if (st == dr){
        mp_max[make_pair(tt[w[lc][st]] , w[lc][st])] = aint[lc][nod].first.first;
        mp_min[make_pair(tt[w[lc][st]] , w[lc][st])] = aint[lc][nod].second.first;
        return;
    }

    query (lc , 2 * nod , st , mid);
    query (lc , 2 * nod + 1 , mid + 1 , dr);

}

int cuplez (int nod){
    int i,vecin;
    if (f[nod])
        return 0;
    f[nod]=1;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (!r[vecin]){ /// il cuplez direct
            lft[nod]=vecin;
            r[vecin]=nod;
            return 1;
        }
    }
    f[nod]=1;
    /// altfel, caut alta modalitate
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (cuplez (r[vecin])){ /// il pot cupla pe nod cu vecin
            lft[nod]=vecin;
            r[vecin]=nod;
            return 1;
        }
    }
    return 0;
}
int cauta (int x , int q){
    int st , dr , mid;

    st = 1;
    dr = q;

    while (st <= dr){
        mid = (st + dr)/2;
        if (op[mid].val == x){
            return mid;
        }
        else if (op[mid].val < x){
            dr = mid - 1;
        }
        else st = mid + 1;
    }

    return 0;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , x , y , powe , p , vecin , q , nr , ok;
    char c;
    pair <int,int> z , p1 , p2;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i < n ; i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    lvl[1] = 1;
    dfs_lant (1);

    for (i = 2 ; i <= n ; i++)
        logg[i] = 1 + logg[i / 2];


    for (powe = 1 ; (1 << powe) <= n ; powe++){
        for (i = 1 ; i <= n ; i++){

            rmq[powe][i] = rmq[powe - 1][rmq[powe - 1][i]];

        }
    }


    /// fiecare nod al catelea e
    for (i = 1 ; i <= lnt ; ++i){
        reverse(w[i].begin(),w[i].end());
        p=0;
        for (vector <int> :: iterator j = w[i].begin() ; j != w[i].end() ; j++){
            /// pozitia lui din lantul curent
            vecin=*j;
            poz[vecin]=p;
            p++;
        }
        aint[i].resize(w[i].size() * 5);
        build ( i , 1 , 0 , w[i].size() - 1 );
    }

    fscanf (fin,"%d\n",&q);
    for (i = 1 ; i <= q ; i++){
        c = fgetc (fin);
        fscanf (fin,"%d%d%d\n",&op[i].x,&op[i].y,&op[i].val);
        if (c == 'm'){
            op[i].tip = 0; /// minim
        }
        else {
            op[i].tip = 1; /// maxim
        }
    }

    sort (op + 1 , op + q + 1 , cmp_subtask);

    for (i = 1 ; i <= q ; i++){
        if (op[i].tip == 0)
            continue;

        z = lca (n , op[i].x , op[i].y);

        if (-1 != z.first)
            update (op[i].x , z.first , op[i].val , 1);
        if (-1 != z.second)
            update (op[i].y , z.second, op[i].val , 1);


    }

    for (i = q ; i ; i--){
        if (op[i].tip == 1)
            continue;

        /// pt minime , ordinea crescatoare

        z = lca (n , op[i].x , op[i].y);

        if (-1 != z.first)
            update (op[i].x , z.first , op[i].val , 2);
        if (-1 != z.second)
            update (op[i].y , z.second, op[i].val , 2);
    }

    for (i = 1 ; i <= lnt ; i++)
        query (i , 1 , 0 , w[i].size() - 1);

    /// o muchie are 2 valori : un max si un min
    /// eu trb sa aleg pt fiecare daca pun max sau min, asa incat fiecare max sa
    /// apara cel putin o data
    /// si fiecare min sa apara cel putin o data

    /// am vect de operatii deja sortat, fac doar cb

    for (i = 1 ; i <= n ; i++)
        v[i].clear();

    for (i = 2 ; i <= n ; i++){
        //printf ("%d %d %d\n" , i , mp_max[make_pair(tt[i] , i)] , mp_min[make_pair(tt[i] , i)] );
        if (mp_max[make_pair(tt[i] , i)] != INF + 1){
            nr = cauta (mp_max[make_pair(tt[i] , i)] , q);
            v[i].push_back(nr);
        }
        if (mp_min[make_pair(tt[i] , i)] != -1){
            nr = cauta (mp_min[make_pair(tt[i] , i)] , q);
            v[i].push_back(nr);
        }
    }

    do{
        ok=0;
        f.reset();
        for (i = 1 ; i <= n ; i++){
            if (!lft[i])
                ok=(ok|cuplez(i));
        }
    }
    while (ok==1);

    for (i = 2 ; i <= n ; i++){
        if (lft[i]){
            fprintf (fout,"%d %d %d\n" , i , tt[i] , op[lft[i]].val);
        }
        else {
            fprintf (fout,"%d %d %d\n", i , tt[i] , mp_max[make_pair(tt[i] , i)]);
        }
    }




    return 0;
}

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

minmaxtree.cpp: In function 'void dfs_lant(int)':
minmaxtree.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();++i){
              ~^~~~~~~~~~~~~~
minmaxtree.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();++i){
                  ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int cuplez(int)':
minmaxtree.cpp:215:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
minmaxtree.cpp:225:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:262:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
minmaxtree.cpp:264:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
minmaxtree.cpp:298:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d\n",&q);
     ~~~~~~~^~~~~~~~~~~~~~~
minmaxtree.cpp:301:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d%d\n",&op[i].x,&op[i].y,&op[i].val);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42