Source code for submission s1109

Go to diff to previous submission

fr.cpp

  1. #include <cstdio>
  2. #include <queue>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. int N, C;
  9.  
  10. struct Dvojice
  11. {
  12.     int vrchol;
  13.     int cena;
  14. };
  15.  
  16. struct Prvek
  17. {
  18.     int index;
  19.     bool existuje;
  20.     bool koren;
  21.     vector<Dvojice> sousede;
  22.     int synu;
  23.     int soucet;
  24. } pole[1005];
  25.  
  26. bool vypsano;
  27.  
  28. int main()
  29. {
  30.     int a,b,c;
  31.     Prvek prvek;
  32.     Dvojice dvojice;
  33.  
  34.     while(scanf("%d", &N) != EOF)
  35.     {
  36.         //printf("Nacitani:\n");
  37.         scanf("%d", &C);
  38.  
  39.         vypsano = false;
  40.  
  41.         for(int i=1; i<=N; i++)
  42.         {
  43.             pole[i].index = i;
  44.             pole[i].existuje = true;
  45.             pole[i].koren = false;
  46.             pole[i].soucet = 0;
  47.             pole[i].synu = 0;
  48.             /**
  49.             while(pole[i].sousede.size() > 0)
  50.                 pole[i].sousede.pop_back();
  51.             **/
  52.             pole[i].sousede.clear();
  53.         }
  54.         for(int i=1; i<=N-1; i++)
  55.         {
  56.             //printf("%d-ty:\n", i);
  57.             scanf("%d%d%d", &a, &b, &c);
  58.             /**
  59.             pole[b].otec = a;
  60.             pole[b].value = c;
  61.             pole[b].synu = 0;
  62.             pole[a].synu++;
  63.             pole[b].soucet = 0;
  64.             **/
  65.  
  66.             dvojice.vrchol = b;
  67.             dvojice.cena = c;
  68.             pole[a].sousede.push_back(dvojice);
  69.             pole[a].synu++;
  70.             dvojice.vrchol = a;
  71.             pole[b].sousede.push_back(dvojice);
  72.             pole[b].synu++;
  73.         }
  74.         pole[C].koren = true;
  75.  
  76. /**
  77.         for(int i=1; i<=N; i++)
  78.         {
  79.             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);
  80.             for(int j=0; j<pole[i].sousede.size(); j++)
  81.             {
  82.                 printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
  83.             }
  84.             printf("\n");
  85.         }
  86. **/
  87.  
  88.         /**
  89.         if(N == 2)
  90.         {
  91.             printf("%d\n", pole[1].sousede.at(0).cena);
  92.             continue;
  93.         }
  94.         **/
  95.  
  96.         queue<Prvek> fronta;
  97.         for(int i=1; i<=N; i++)
  98.         {
  99.             if(pole[i].synu == 1 && pole[i].koren == false) // && pole[i].koren == false) // 1 soused
  100.             {
  101.                 pole[i].soucet = 123456789;
  102.                 fronta.push(pole[i]);
  103.                 //printf("frona.push(%d)\n", i);
  104.             }
  105.         }
  106.  
  107.         while(!fronta.empty())
  108.         {
  109.             prvek = fronta.front();
  110.             fronta.pop();
  111.  
  112. /**
  113.             printf("\n\n\n\n\nFRONTA:\n");
  114.             printf("PRVEK[%d]\n", prvek.index);
  115.             for(int i=1; i<=N; i++)
  116.         {
  117.             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);
  118.             for(int j=0; j<pole[i].sousede.size(); j++)
  119.             {
  120.                 printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
  121.             }
  122.             printf("\n");
  123.         }
  124.         printf("\n");
  125. **/
  126.  
  127.  
  128.             if(prvek.koren == false) // ne centralni prvek
  129.             {
  130.                 for(int i=0; i<prvek.sousede.size(); i++)
  131.                 {
  132.                     if(pole[prvek.sousede.at(i).vrchol].existuje == true)
  133.                     {
  134.                         dvojice = prvek.sousede.at(i);
  135.                         break;
  136.                     }
  137.                 }
  138.                 //printf("pole[%d]->otec: [%d,%d]\n", prvek.index, dvojice.vrchol, dvojice.cena);
  139.                 if(prvek.soucet <= dvojice.cena)
  140.                 {
  141.                     pole[dvojice.vrchol].soucet += prvek.soucet;
  142.                     //printf("1) pole[%d].soucet += %d\n", dvojice.vrchol, prvek.soucet);
  143.                 }
  144.                 else
  145.                 {
  146.                     pole[dvojice.vrchol].soucet += dvojice.cena;
  147.                     //printf("2) pole[%d].soucet += %d\n", dvojice.vrchol, dvojice.cena);
  148.                 }
  149.                 pole[prvek.index].existuje = false;
  150.                 pole[dvojice.vrchol].synu--;
  151.                 if(pole[dvojice.vrchol].synu == 1)
  152.                     fronta.push(pole[dvojice.vrchol]); // posledni prikaz bloku!!
  153.             }
  154.             else
  155.             {
  156.                 printf("%d\n", pole[prvek.index].soucet); // VYSLEDEK
  157.                 while(!fronta.empty())
  158.                     fronta.pop();
  159.                 vypsano = true;
  160.                 continue;
  161.             }
  162.  
  163. /**
  164.             printf("KONEC:\n");
  165.             for(int i=1; i<=N; i++)
  166.         {
  167.             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);
  168.             for(int j=0; j<pole[i].sousede.size(); j++)
  169.             {
  170.                 printf("[%d,%d] ", pole[i].sousede.at(j).vrchol, pole[i].sousede.at(j).cena);
  171.             }
  172.             printf("\n");
  173.         }
  174.         **/
  175.         }
  176.  
  177.         if(vypsano == false)
  178.         {
  179.  
  180.             printf("%d\n", pole[C].soucet);
  181.         }
  182.  
  183.         //printf("Konec_Vypoctu\n");
  184.         // ṕro jistotu
  185.         while(!fronta.empty())
  186.             fronta.pop();
  187.  
  188.     }
  189.  
  190.     return 0;
  191. }
  192.  

Diff to submission s1057

fr.cpp

--- c5.s1057.cteam093.fr.cpp.0.fr.cpp
+++ c5.s1109.cteam093.fr.cpp.0.fr.cpp
@@ -24,4 +24,6 @@
 } pole[1005];
 
+bool vypsano;
+
 int main()
 {
@@ -35,4 +37,6 @@
         scanf("%d", &C);
 
+        vypsano = false;
+
         for(int i=1; i<=N; i++)
         {
@@ -82,4 +86,5 @@
 **/
 
+        /**
         if(N == 2)
         {
@@ -87,9 +92,10 @@
             continue;
         }
+        **/
 
         queue<Prvek> fronta;
         for(int i=1; i<=N; i++)
         {
-            if(pole[i].synu == 1) // && pole[i].koren == false) // 1 soused
+            if(pole[i].synu == 1 && pole[i].koren == false) // && pole[i].koren == false) // 1 soused
             {
                 pole[i].soucet = 123456789;
@@ -149,5 +155,8 @@
             {
                 printf("%d\n", pole[prvek.index].soucet); // VYSLEDEK
-                break;
+                while(!fronta.empty())
+                    fronta.pop();
+                vypsano = true;
+                continue;
             }
 
@@ -166,4 +175,10 @@
         }
 
+        if(vypsano == false)
+        {
+
+            printf("%d\n", pole[C].soucet);
+        }
+
         //printf("Konec_Vypoctu\n");
         // ṕro jistotu