Source code for submission s760

Go to diff to previous submission

fn.cpp

  1. #include <stdio.h>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector <int> v;
  7. vector <int> un;
  8. vector <int> vysl;
  9. vector <int> velk;
  10.  
  11. int find(int a){
  12.  
  13. 	while(un[a]!=a){
  14. 		a = un[a];
  15. 	}
  16.  
  17. 	return a;
  18. }
  19.  
  20. void uni(int a, int b){
  21. 	int aa = find(a);
  22. 	int bb = find(b);
  23.  
  24. 	if(aa!=bb){
  25. 		if(velk[aa] <= velk[bb]){
  26. 			un[aa] = bb;
  27. 			velk[bb] += velk[aa];
  28. 		}
  29. 		else{
  30. 			un[bb] = aa;
  31. 			velk[aa] += velk[bb];
  32. 		}
  33.  
  34. 	}
  35.  
  36. }
  37.  
  38.  
  39.  
  40.  
  41. int main(){
  42.  
  43. 	int n,m,a,b;
  44.  
  45. 	while(scanf("%d %d", &n,&m) == 2){
  46. 		int uspech = 0;
  47.  
  48. 		v.clear();
  49. 		un.clear();
  50. 		vysl.clear();
  51.  
  52. 		//vector<int> h(n);
  53.  
  54. 		for(int i=0; i<n; i++){
  55. 			v.push_back(0);
  56. 			un.push_back(i);
  57. 			vysl.push_back(0);
  58. 			velk.push_back(1);			
  59. 			//h[i]=0;
  60. 		}
  61.  
  62. 		for(int i = 0; i<m; i++){
  63. 			scanf("%d %d", &a,&b);
  64. 			a--;
  65. 			b--;
  66.  
  67. 			v[a]++;
  68. 			v[b]++;
  69.  
  70. 			uni(a,b);
  71.  		}
  72.  
  73.  		for(int i=0; i<n; i++){
  74.  			int koren;
  75.  
  76.  			if(v[i]==1){
  77.  				koren = find(i);
  78.  				vysl[koren]++;
  79.  			}
  80.  
  81.  			if(vysl[koren] >= 4){
  82.  				uspech = 1;
  83.  			}
  84.  
  85.  		}
  86.  
  87.  		/*
  88.  		printf("v: ");
  89.  		for(int i=0; i<n; i++){
  90.  			printf("%d ", v[i]);
  91.  		}
  92.  		printf("\n");
  93.  		
  94.  		printf("un: ");
  95.  		for(int i=0; i<n; i++){
  96.  			printf("%d ", un[i]);
  97.  		}
  98.  		printf("\n");
  99.  		
  100.  		printf("vysl: ");
  101.  		for(int i=0; i<n; i++){
  102.  			printf("%d ", vysl[i]);
  103.  		}
  104.  		printf("\n");
  105.  		*/
  106.  
  107.  		if(uspech == 1){
  108.  			printf("YES\n");
  109.  		}
  110.  		else
  111.  		{
  112.  			printf("NO\n");
  113.  		}
  114.  
  115. 	}
  116.  
  117. 	return 0;
  118. }
  119.  

Diff to submission s756

fn.cpp

--- c5.s756.cteam077.fn.cpp.0.fn.cpp
+++ c5.s760.cteam077.fn.cpp.0.fn.cpp
@@ -85,4 +85,5 @@
                 }
                 
+                /*
                 printf("v: ");
                 for(int i=0; i<n; i++){
@@ -102,5 +103,5 @@
                 }
                 printf("\n");
-                
+                */
                 
                 if(uspech == 1){