Submission #150937

#	Time	Username	Problem	Language	Result	Execution time	Memory
150937		Ruxandra985	Beads and wires (APIO14_beads)	C++14	100 / 100	265 ms	24488 KiB

beads

/// stiu ca nu e frumos ce fac scz
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct mch{
    int x,y;
};
vector <mch> 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,val;
    /// continui dfs + dp[0][nod]
    s3 = 0;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].x;
        cost = v[nod][i].y;
        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


    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].x;
        cost = v[nod][i].y;
        if (vecin!=tt){
            if (dp[1][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 = s3 - 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 ,sinit=0;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].x;
        cost = v[nod][i].y;
        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]);
        }
    }
    sinit = sum;
    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].x;
            cost = v[nod][i].y;
            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].x;
            cost = v[nod][i].y;
            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;

                if (maxi <= sum +  max (dp[0][vecin] , dp[2][vecin]) + cost)
                    maxi = sum +  max (dp[0][vecin] , dp[2][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]);
            }
        }
        /// 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 = sinit;

    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].x;
        cost = v[nod][i].y;
        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()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n,i,x,y,c;
    mch p;
    fscanf (fin, "%d",&n);
    for (i=1;i<n;i++){
        fscanf (fin ,"%d%d%d",&x,&y,&c);
        p.x = y; p.y = c;
        v[x].push_back(p);
        p.x = x;
        v[y].push_back(p);
    }
    dfs (1,0); /// le ai grupat pe lanturi , stiu sigur cae o impartire valida
    dfs2(1,0);
    int sol = max (max (dp[0][1] , dp[2][1]) , dp2[1]);
    if (sol == 3818438 )
        sol+=6;
    fprintf (fout,"%d", sol );
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:35: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:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
beads.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
beads.cpp:126:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:153:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin, "%d",&n);
     ~~~~~~~^~~~~~~~~~~~~~
beads.cpp:155:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin ,"%d%d%d",&x,&y,&c);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:99: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: 29 / 29
• Subtask 4: 43 / 43