Source code for submission s1057

Go to diff to previous submission

#include <cstdio>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, C;
 
struct Dvojice
{
    int vrchol;
    int cena;
};
 
struct Prvek
{
    int index;
    bool existuje;
    bool koren;
    vector<Dvojice> sousede;
    int synu;
    int soucet;
} pole[1005];
 
int main()
{
    int a,b,c;
    Prvek prvek;
    Dvojice dvojice;
 
    while(scanf("%d", &N) != EOF)
    {
        //printf("Nacitani:\n");
        scanf("%d", &C);
 
        for(int i=1; i<=N; i++)
        {
            pole[i].index = i;
            pole[i].existuje = true;
            pole[i].koren = false;
            pole[i].soucet = 0;
            pole[i].synu = 0;
            /**
            while(pole[i].sousede.size() > 0)
                pole[i].sousede.pop_back();
            **/
            pole[i].sousede.clear();
        }
        for(int i=1; i<=N-1; i++)
        {
            //printf("%d-ty:\n", i);
            scanf("%d%d%d", &a, &b, &c);
            /**
            pole[b].otec = a;
            pole[b].value = c;
            pole[b].synu = 0;
            pole[a].synu++;
            pole[b].soucet = 0;
            **/
 
            dvojice.vrchol = b;
            dvojice.cena = c;
            pole[a].sousede.push_back(dvojice);
            pole[a].synu++;
            dvojice.vrchol = a;
            pole[b].sousede.push_back(dvojice);
            pole[b].synu++;
        }
        pole[C].koren = true;
 
/**
        for(int i=1; i<=N; i++)
        {
            printf("%d) index=%d exist=%d koren=%d synu=%d souc=%d ... ", i, pole[i].index, pole[i].existuje, pole[i].koren, pole[i].synu, pole[i].soucet);
            for(int j=0; j<pole[i].sousede.size(); j++)
            {
                printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
            }
            printf("\n");
        }
**/
 
        if(N == 2)
        {
            printf("%d\n", pole[1].sousede.at(0).cena);
            continue;
        }
 
        queue<Prvek> fronta;
        for(int i=1; i<=N; i++)
        {
            if(pole[i].synu == 1) // && pole[i].koren == false) // 1 soused
            {
                pole[i].soucet = 123456789;
                fronta.push(pole[i]);
                //printf("frona.push(%d)\n", i);
            }
        }
 
        while(!fronta.empty())
        {
            prvek = fronta.front();
            fronta.pop();
 
/**
            printf("\n\n\n\n\nFRONTA:\n");
            printf("PRVEK[%d]\n", prvek.index);
            for(int i=1; i<=N; i++)
        {
            printf("%d) index=%d exist=%d koren=%d synu=%d souc=%d ... ", i, pole[i].index, pole[i].existuje, pole[i].koren, pole[i].synu, pole[i].soucet);
            for(int j=0; j<pole[i].sousede.size(); j++)
            {
                printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
            }
            printf("\n");
        }
        printf("\n");
**/
 
 
            if(prvek.koren == false) // ne centralni prvek
            {
                for(int i=0; i<prvek.sousede.size(); i++)
                {
                    if(pole[prvek.sousede.at(i).vrchol].existuje == true)
                    {
                        dvojice = prvek.sousede.at(i);
                        break;
                    }
                }
                //printf("pole[%d]->otec: [%d,%d]\n", prvek.index, dvojice.vrchol, dvojice.cena);
                if(prvek.soucet <= dvojice.cena)
                {
                    pole[dvojice.vrchol].soucet += prvek.soucet;
                    //printf("1) pole[%d].soucet += %d\n", dvojice.vrchol, prvek.soucet);
                }
                else
                {
                    pole[dvojice.vrchol].soucet += dvojice.cena;
                    //printf("2) pole[%d].soucet += %d\n", dvojice.vrchol, dvojice.cena);
                }
                pole[prvek.index].existuje = false;
                pole[dvojice.vrchol].synu--;
                if(pole[dvojice.vrchol].synu == 1)
                    fronta.push(pole[dvojice.vrchol]); // posledni prikaz bloku!!
            }
            else
            {
                printf("%d\n", pole[prvek.index].soucet); // VYSLEDEK
                break;
            }
 
/**
            printf("KONEC:\n");
            for(int i=1; i<=N; i++)
        {
            printf("%d) index=%d exist=%d koren=%d synu=%d souc=%d ... ", i, pole[i].index, pole[i].existuje, pole[i].koren, pole[i].synu, pole[i].soucet);
            for(int j=0; j<pole[i].sousede.size(); j++)
            {
                printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
            }
            printf("\n");
        }
        **/
        }
 
        //printf("Konec_Vypoctu\n");
        // ṕro jistotu
        while(!fronta.empty())
            fronta.pop();
 
    }
 
    return 0;
}
 

Diff to submission s1023

--- c5.s1023.cteam093.fr.cpp.0.fr.cpp
+++ c5.s1057.cteam093.fr.cpp.0.fr.cpp
@@ -82,9 +82,14 @@
 **/
 
+        if(N == 2)
+        {
+            printf("%d\n", pole[1].sousede.at(0).cena);
+            continue;
+        }
 
         queue<Prvek> fronta;
         for(int i=1; i<=N; i++)
         {
-            if(pole[i].synu == 1) // 1 soused
+            if(pole[i].synu == 1) // && pole[i].koren == false) // 1 soused
             {
                 pole[i].soucet = 123456789;