Submission #147987

#	Time	Username	Problem	Language	Result	Execution time	Memory
147987		Ruxandra985	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	5112 KiB

beads

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair <int,int> > v[200010];
int dp[4][200010];
void dfs (int nod,int tt){

    /// 0 -> nod nu a fost luat
    /// 1 -> nod e mijloc in lant
    /// 2 -> nod e mijloc in triunghi (e si mijloc si cel mai de sus)
    /// 3 -> nod e cel mai de sus dintr un lant luat

    int i,s3=0,other=0,chosen,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] , max (dp[2][vecin] , dp[3][vecin]));
            if (dp[1][vecin])
                s3 = s3 + max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , max (dp[2][vecin] , dp[3][vecin]));
            else s3 = s3 + max ( dp[0][vecin] , max (dp[2][vecin] , dp[3][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) , max (dp[2][vecin] , dp[3][vecin]));
            else other = sum - max ( dp[0][vecin] , max (dp[2][vecin] , dp[3][vecin]));
            val = max (dp[0][vecin] , max(dp[2][vecin] , dp[3][vecin]));
            if (dp[1][nod] < other + val + cost){
                chosen = vecin;
                dp[1][nod] = other + val + cost;
            }
        }
    }

    /// dp[2][nod] -> alegi doi vecini pe care sa ii iei obligatoriu cu 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])
                other = dp[1][nod] - max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , max (dp[2][vecin] , dp[3][vecin]));
            else other = dp[1][nod] - max ( dp[0][vecin] , max (dp[2][vecin] , dp[3][vecin]));
            val = max (dp[0][vecin] , max(dp[2][vecin] , dp[3][vecin]));
            if (dp[2][nod] < other + val + cost){
                dp[2][nod] = other + val + cost;
            }
        }
    }


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



    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        cost = v[nod][i].second;
        if (vecin!=tt && dp[1][vecin]){
            other = s3 - max ( max ( dp[0][vecin] , dp[1][vecin] + cost) , max (dp[2][vecin] , dp[3][vecin]));
            dp[3][nod] = max ( dp[3][nod] , other + dp[1][vecin] + cost);
        }
    }
}
int main()
{
   // FILE *fin = fopen ("a.in","r");
   // FILE *fout = fopen ("a.out","w");
    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);
    printf ("%d",max (dp[0][1] , max (dp[2][1] , dp[3][1])));
    /// nu poate fi mijloc in lant
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:18: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:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:69: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:83:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
beads.cpp:85: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 dfs(int, int)':
beads.cpp:53:31: warning: 'chosen' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (vecin!=tt && vecin!=chosen){
                          ~~~~~^~~~~~~~

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