Submission #150918

#	Time	Username	Problem	Language	Result	Execution time	Memory
150918		Ruxandra985	구슬과 끈 (APIO14_beads)	C++14	28 / 100	10 ms	5496 KiB

beads

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair <int,int> > v[200010];
int dp[3][200010];
int dp2[200010],aux[200010];
void dfs (int nod,int tt){ /// ne prefacem ca nu putem avea triunghiuri
    /// 0 -> nod nu a fost luat
    /// 1 -> nod e mijloc in lant
    /// 2 -> nod e cel mai de sus dintr un lant luat

    int i,s3=0,other=0,vecin,cost,sum,val;

    /// continui dfs + dp[0][nod]
    s3 = 0;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        cost = v[nod][i].second;
        if (vecin != tt){
            dfs (vecin , nod);
            dp[0][nod] += max (dp[0][vecin] , dp[2][vecin]);
            if (dp[1][vecin])
                s3 = s3 + max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , dp[2][vecin]);
            else s3 = s3 + max ( dp[0][vecin] , dp[2][vecin] );
        }
    }

    /// dp[1][nod] -> alegi un vecin pe care il iei obligatoriu cu 0

    sum = s3;

    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        cost = v[nod][i].second;
        if (vecin!=tt){
            if (dp[1][vecin]){
                other = sum - max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , dp[2][vecin]);
                other = s3 - max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , dp[2][vecin]);
                dp[2][nod] = max ( dp[2][nod] , other + dp[1][vecin] + cost);
            }
            else other = sum - max ( dp[0][vecin] , dp[2][vecin]);
            val = max (dp[0][vecin] , dp[2][vecin]);
            dp[1][nod] = max (dp[1][nod] , other + val + cost );
        }
    }


    /// dp[2][nod] -> alegi cati vecini vrei cu 1 , CEL PUTIN UNUL

}

void dfs2 (int nod,int tt){
    int vecin , cost , chosen , ok , maxi , i , fii = 0 , sum=0 , ok2 , chosen2;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        cost = v[nod][i].second;
        if (vecin!=tt){
            dfs2(vecin , nod);
            fii++;
            if (dp[1][vecin])
                sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
            else sum += max (dp[0][vecin] , dp[2][vecin]);
        }
    }
    /// ce se intampla daca vreau sa il fac pe nod mijloc intr un triunghi
    /// intre doi fii de ai lui nod , a existat o muchie si noi am adaugat nod
    /// avand in vedere ca exista muchie, ins ca un subarbore era initial gol
    /// daca un subarbore era gol , inseamna ca a fost obtinut cu prm dfs???
    //if (nod == 10)
      //  printf ("a");
    if ( fii >= 2 ){ /// dp2 presupune existenta a doi fii

        maxi = 0;
        ok = 0;
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i].first;
            cost = v[nod][i].second;
            if (vecin!=tt){
                if (dp[1][vecin])
                    sum -= max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
                else sum -= max (dp[0][vecin] , dp[2][vecin]);
                if (maxi < sum + dp2[vecin] + cost){
                    maxi = sum + dp2[vecin] + cost;
                    chosen = vecin;
                    ok = 1;
                }
                if (maxi <= sum + max (dp[0][vecin] , dp[2][vecin]) + cost){
                    maxi = sum + max (dp[0][vecin] , dp[2][vecin]) + cost;
                    chosen = vecin;
                    ok = 0;
                }
                if (dp[1][vecin])
                    sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
                else sum += max (dp[0][vecin] , dp[2][vecin]);
            }
        }
        sum = maxi;
        maxi = 0;
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i].first;
            cost = v[nod][i].second;
            if (vecin!=tt && vecin!=chosen){

                if (dp[1][vecin])
                    sum -= max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
                else sum -= max (dp[0][vecin] , dp[2][vecin]);

                if (maxi < sum + dp2[vecin] + cost && ok == 0){
                    maxi = sum + dp2[vecin] + cost;
                    ok2 = 1;
                    chosen2 = vecin;
                }
                if (maxi <= sum +  max (dp[0][vecin] , dp[2][vecin]) + cost){
                    maxi = sum +  max (dp[0][vecin] , dp[2][vecin]) + cost;
                    ok2 = 0;
                    chosen2 = vecin;
                }

                if (dp[1][vecin])
                    sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
                else sum += max (dp[0][vecin] , dp[2][vecin]);
            }
        }
        /// maxi = cat ai obtine daca NOD ar fi mijloc
        /// cand ai un triunghi , tu adaugi o muchie IN SUS
        dp2[nod]=maxi;
    }
    /// dar daca nod nu ar fi fix varful triunghiului , dar ar fi triunghuri in
    /// subarborii lui

    sum = 0;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        cost = v[nod][i].second;
        if (vecin!=tt){
            if (dp[1][vecin])
                sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
            else sum += max (dp[0][vecin] , dp[2][vecin]);
        }
    }

    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        cost = v[nod][i].second;
        if (vecin!=tt){
            if (dp[1][vecin])
                sum -= max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
            else sum -= max (dp[0][vecin] , dp[2][vecin]);
            if (dp2[vecin])
                aux[nod] = max (aux[nod] , sum + dp2[vecin] + cost);
            dp2[nod] = max ( dp2[nod] , sum + dp2[vecin] ); /// rosie
            if (aux[vecin])
                dp2[nod] = max (dp2[nod] , sum + aux[vecin] + cost);
            if (dp[1][vecin])
                sum += max (dp[0][vecin] , max (dp[2][vecin] , dp[1][vecin] + cost));
            else sum += max (dp[0][vecin] , dp[2][vecin]);
        }
    }


}

int main()
{
   // freopen ("a.in" , "r" , stdin);
   // freopen ("a.out" , "w" , stdout);
    int n,i,x,y,c;
    scanf ("%d",&n);
    for (i=1;i<n;i++){
        scanf ("%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    dfs (1,0); /// le ai grupat pe lanturi , stiu sigur cae o impartire valida
    dfs2(1,0);
    printf ("%d", max (max (dp[0][1] , dp[2][1]) , dp2[1]));
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
beads.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
beads.cpp:133:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:143:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:54:67: warning: variable 'ok2' set but not used [-Wunused-but-set-variable]
     int vecin , cost , chosen , ok , maxi , i , fii = 0 , sum=0 , ok2 , chosen2;
                                                                   ^~~
beads.cpp:54:73: warning: variable 'chosen2' set but not used [-Wunused-but-set-variable]
     int vecin , cost , chosen , ok , maxi , i , fii = 0 , sum=0 , ok2 , chosen2;
                                                                         ^~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:169:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
beads.cpp:171:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d%d%d",&x,&y,&c);
         ~~~~~~^~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:103:35: warning: 'chosen' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (vecin!=tt && vecin!=chosen){
                              ~~~~~^~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43