제출 #216455

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

minmaxtree

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

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;
vector <int> v[DIMN] , w[DIMN];
vector <pair <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 fth){
    int i,vecin,ok=0,maxi,fiu;
    tt[nod] = fth;
    rmq[0][nod] = fth;
    d[nod] = 1;
    maxi=0;
    fiu=0;
    for (i=0;i<v[nod].size();++i){
        vecin=v[nod][i];
        if (vecin!=fth){
            ok=1;
            lvl[vecin] = 1 + lvl[nod];
            dfs_lant(vecin , nod);
            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!=fth && 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].second.second = w[lc][st];
        return;
    }

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

    aint[nod] = aint[2 * nod];

}

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

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

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

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

}

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

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

    aint[lc][node] = min( aint[lc][2 * node] , aint[lc][2 * node + 1] );


}
void update (int x , int y , int val){
    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);
            update ( up[l[x]] , y , val);
        }
        else{
            update ( x , up[l[y]] , val );

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

pair <int,int> query_aint (int lc, int node , int st , int dr , int px , int py){
    int mid;
    pair <int,int> sol = make_pair(1000000000 , 0);
    update_lazy(lc , node , st , dr);
    if (px <= st && dr <= py){
        return make_pair(aint[lc][node].first , aint[lc][node].second.second);
    }
    mid = ((st + dr)>>1);
    update_lazy(lc , 2 * node , st , mid);
    update_lazy(lc , 2 * node + 1 , mid + 1 , dr);


    if (px <= mid)
        sol = min( sol , query_aint(lc , 2 * node , st , mid , px , py) );
    if (mid+1 <= py)
        sol = min( sol , query_aint(lc , 2 * node + 1 , mid + 1 , dr , px , py));

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

    return sol;
}
pair <int,int> query (int x , int y){
    if (l[x] != l[y]){ /// avansam
        if (lvl[up[l[x]]]>lvl[up[l[y]]]){
            return min( query(up[l[x]] , y) , query_aint(l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x]));
        }
        else{
            return min( query(x , up[l[y]]) , query_aint(l[y] , 1 , 0 , w[l[y]].size()-1 , 0 , poz[y]));
        }
    }
    else{
        return query_aint(l[x] , 1 , 0 , w[l[x]].size()-1 , min(poz[x],poz[y]) , max(poz[x],poz[y]));
    }
}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , x , y , powe , p , ok , vecin , q , node;
    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 , 0);

    for (i = 2 ; i <= 2 * 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);
    ok = 1;
    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
            ok = 0;
        }
        else {
            op[i].tip = 1; /// maxim
        }
    }

    if (ok){ /// ai doar maxime

        for (i = 1 ; i <= q ; i++){
            z = lca (n , op[i].x , op[i].y);

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

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

        for (i = 1 ; i <= q ; i++){

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

            p1 = p2 = make_pair(1000000000 , 0);

            if (-1 != z.first)
                p1 = query (op[i].x , z.first);
            if (-1 != z.second)
                p2 = query (op[i].y , z.second);

            if (p1.first <= p2.first)
                node = p1.second;
            else node = p2.second;



            mp[make_pair(node , tt[node])] = op[i].val;

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

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


        }

        for (i = 2 ; i <= n ; i++){
            if (mp[make_pair(i , tt[i])] == 0)
                fprintf (fout,"%d %d 1\n" , i , tt[i]);
            else fprintf (fout,"%d %d %d\n" , i , tt[i] , mp[make_pair(i , tt[i])]);
        }

    }

    return 0;
}

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

minmaxtree.cpp: In function 'void dfs_lant(int, int)':
minmaxtree.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();++i){
              ~^~~~~~~~~~~~~~
minmaxtree.cpp:75:19: 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:209: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:211: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:245: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:249: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: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42