Submission #150868

#	Time	Username	Problem	Language	Result	Execution time	Memory
150868		Ruxandra985	구슬과 끈 (APIO14_beads)	C++14	0 / 100	6 ms	5112 KiB

beads

/// vreau doar sa incerc oricum e o sursa foarte messy bleah problema asta ma frustreaza
/// logic pt ca e dinamica pe arbore si cumva rux nu stie dinamici pe arbore hahaha
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair <int,int> > v[200010];
int dp[3][200010];
int dp2[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]);
            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



    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) , dp[2][vecin]);
            dp[2][nod] = max ( dp[2][nod] , other + dp[1][vecin] + cost);
        }
    }
}

void dfs2 (int nod,int tt){
    int vecin , cost , chosen , ok , maxi , i , fii = 0 , sum;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        if (vecin!=tt){
            dfs2(vecin , nod);
            fii++;
        }
    }
    /// 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 ( fii < 2 ){ /// dp2 presupune existenta a doi fii
        return;
    }
    sum = 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]);
        }
    }
    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;
            }
            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]);
        }
    }
    dp2[nod]+=maxi;


}

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:19: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:52: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:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
beads.cpp:114: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:145:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
beads.cpp:147: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:82: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