Source code for submission s1018

Go to diff to previous submission

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <sstream>
 
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
 
using namespace std;
 
vector <int> v;
vector < vector < pair<int, int> > > hrany;
 
int bla(int koren){	
	//printf("Som vo vrchole: %d\n", koren+1);
 
	v[koren] = 1;
	int pocet_veducich = 0;
	int le = hrany[koren].size();
 
	for(int i = 0; i< le; i++){
		if(v[hrany[koren][i].first] == 0) pocet_veducich++;	
	}
 
	if(pocet_veducich > 0){
		int suma = 0;
 
		for(int i = 0; i< le; i++){
 
			if(v[hrany[koren][i].first] == 0){
				//printf("Idem do: %d z %d\n", hrany[koren][i].first+1, koren+1);
				suma += min(hrany[koren][i].second, bla(hrany[koren][i].first)); 
			}
 
		}
 
		return suma;
	}
	else return 7000000;
}
 
 
 
int main(){
 
	int n, koren;
	while(scanf("%d %d", &n, &koren) == 2){
			int a,b,h;
			koren--;
 
			v.resize(n);
 
			for(int i = 0; i< n; i++){
				v[i]=0;
			}
 
 
			hrany.resize(n);
 
			int pocet_hran = n-1;
 
			while(pocet_hran--){
				scanf("%d %d %d", &a, &b, &h);
				a--;
				b--;
 
				hrany[a].push_back(make_pair(b,h));
				hrany[b].push_back(make_pair(a,h));
 
			}
 
 
			printf("%d\n", bla(koren));
			v.clear();
			hrany.clear();
 
	}
 
	return 0;
}
 

Diff to submission s910

--- c5.s910.cteam077.fr.cpp.0.fr.cpp
+++ c5.s1018.cteam077.fr.cpp.0.moj.cpp
@@ -4,5 +4,4 @@
 #include <vector>
 #include <set>
-#include <queue>
 #include <map>
 #include <string>
@@ -20,66 +19,72 @@
 using namespace std;
 
-#define X first
-#define Y second
-#define MP make_pair
-#define PB push_back
-#define SZ size
+vector <int> v;
+vector < vector < pair<int, int> > > hrany;
 
-int main () {
-        int hodnota[1005];
-        int pom[1005], pom2[1005];
-        int hrany[1005][1005];
-        int sus[1005][1005];
-        queue<int> t;
+int bla(int koren){     
+        //printf("Som vo vrchole: %d\n", koren+1);
         
-        int i, ii, n, koren, a, b, c;
-        while (scanf("%d %d", &n, &koren) > 0) {
-                for (i = 1; i < 1002; i++) {
-                        pom[i] = 0;
-                        hodnota[i] = 0;
-                        pom2[i] = 0;
-                }
-                for (i = 1; i < 1002; i++) {
-                        for (ii = 1; ii < 1002; ii++) {
-                                hrany[i][ii] = 0;
+        v[koren] = 1;
+        int pocet_veducich = 0;
+        int le = hrany[koren].size();
+                
+        for(int i = 0; i< le; i++){
+                if(v[hrany[koren][i].first] == 0) pocet_veducich++;     
+        }
+        
+        if(pocet_veducich > 0){
+                int suma = 0;
+                
+                for(int i = 0; i< le; i++){
+                
+                        if(v[hrany[koren][i].first] == 0){
+                                //printf("Idem do: %d z %d\n", hrany[koren][i].first+1, koren+1);
+                                suma += min(hrany[koren][i].second, bla(hrany[koren][i].first)); 
                         }
+                        
                 }
-                for (i = 0; i < n - 1; i++) {
-                        scanf("%d %d %d", &a, &b, &c);
-                        pom[a] = pom[a] + 1;
-                        pom[b] = pom[b] + 1;
-                        //cout << pom[1] << endl;
-                        hrany[a][b] = c;
-                        hrany[b][a] = c;
-                        sus[a][pom[a] - 1] = b;
-                        sus[b][pom[b] - 1] = a;
-                        pom2[a] = pom2[a] + 1;
-                        pom2[b] = pom2[b] + 1;
-                }
-                for (i = 1; i <= n; i++) {
-                        if (pom[i] == 1 && i != koren)
-                                t.push(i);
-                }
-                while(!t.empty()) {
-                        n = t.front();
-                        t.pop();
+                
+                return suma;
+        }
+        else return 7000000;
+}
+
+
+
+int main(){
+
+        int n, koren;
+        while(scanf("%d %d", &n, &koren) == 2){
+                        int a,b,h;
+                        koren--;
                         
-                        //cout << n << "aaa" << pom[1] << endl;
-                        for (ii = 0; ii < pom[n]; ii++) {
-                                
-                                //cout << sus[n][ii] << "bbb" << endl;
-                                if (hodnota[n] == 0 || hodnota[n] > hrany[n][sus[n][ii]]) 
-                                        hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hrany[n][sus[n][ii]];
-                                else
-                                        hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hodnota[n];
-                                pom2[sus[n][ii]]--;
-                                if (pom2[sus[n][ii]] == 1)
-                                        t.push(sus[n][ii]);
-                                //cout << sus[n][ii] << " " << hodnota[sus[n][ii]] << " " << n << endl;
+                        v.resize(n);
+                        
+                        for(int i = 0; i< n; i++){
+                                v[i]=0;
                         }
-                        pom2[n] = -1;
-                }
-                cout << hodnota[koren] << endl;
-        }
+                        
+                        
+                        hrany.resize(n);
+        
+                        int pocet_hran = n-1;
+                        
+                        while(pocet_hran--){
+                                scanf("%d %d %d", &a, &b, &h);
+                                a--;
+                                b--;
+                
+                                hrany[a].push_back(make_pair(b,h));
+                                hrany[b].push_back(make_pair(a,h));
+                        
+                        }
+                        
+                        
+                        printf("%d\n", bla(koren));
+                        v.clear();
+                        hrany.clear();
+                        
+        }
+
         return 0;
 }