fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <fstream>
  9. #include <vector>
  10. #include <queue>
  11. #include <deque>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <complex>
  16. #include <string>
  17. #define REP(i,j) for(int i=1;i<=j;++i)
  18. #define REPI(i,j,k) for(int i=j;i<=k;++i)
  19. #define REPD(i,j) for(int i=j;0<i;--i)
  20. #define CLR(s) memset(s,0,sizeof s)
  21. #define SET(s,v) memset(s,v,sizeof s)
  22. #define mp make_pair
  23. #define pb push_back
  24. #define x first
  25. #define y second
  26. using namespace std;
  27. string FILE_NAME = "meat";
  28. typedef long long LL;
  29. typedef double DB;
  30. const int INF = 0x3f3f3f3f;
  31.  
  32. const int maxn = 2000 + 100;
  33.  
  34. int fa[maxn],son[maxn],n;
  35. DB A[maxn];
  36. struct Edge
  37. {
  38. 	int head[maxn],next[maxn],to[maxn];
  39. 	int edge;
  40. 	void init()
  41. 	{
  42. 		edge=0;
  43. 		SET(head,-1);
  44. 	}
  45. 	void addedge(int a,int b)
  46. 	{
  47. 		next[edge]=head[a];
  48. 		to[edge]=b;
  49. 		head[a]=edge++;
  50. 	}
  51. }E;
  52.  
  53. int cnt;
  54.  
  55. int dcmp(DB d)
  56. {
  57. 	if(fabs(d)<1e-4)
  58. 		return 0;
  59. 	return d<0?-1:1;
  60. }
  61.  
  62.  
  63. void get_son(int f,DB wei)
  64. {
  65. 	if(son[f]==0)
  66. 		return ;
  67. 	DB ave=wei/son[f];
  68. 	for(int i=E.head[f];i!=-1;i=E.next[i])
  69. 	{
  70. 		if(dcmp(A[E.to[i]]-ave)!=0)
  71. 		{
  72. 			++cnt;
  73. 		}
  74. 		get_son(E.to[i],ave);
  75. 	}
  76. }
  77.  
  78. int get_num(int ex)
  79. {
  80. 	cnt=0;
  81. 	DB wei=A[ex];
  82. 	while(ex!=1)
  83. 	{
  84. 		wei=wei*son[fa[ex]];
  85. 		ex=fa[ex];
  86. 	}
  87. 	if(dcmp(wei-A[ex])!=0) cnt=1;
  88. 	get_son(1,wei);
  89. //	printf("%d %lf %d\n",ex,wei,cnt);
  90. 	return cnt;
  91. }
  92.  
  93. int main()
  94. {
  95. 	scanf("%d",&n);
  96. 	E.init();
  97. 	for(int i=1;i<=n;++i)
  98. 	{
  99. 		scanf("%lf",&A[i]);
  100. 	}
  101. 	for(int i=1;i<n;++i)
  102. 	{
  103. 		int a,b;
  104. 		scanf("%d%d",&a,&b);
  105. 		fa[b]=a;
  106. 		++son[a];
  107. 		E.addedge(a,b);
  108. 	}
  109.  
  110. 	int ans=INF;
  111. 	for(int i=n;0<i;--i)
  112. 	{
  113. 		int d=get_num(i);
  114. 		if(d<ans) ans=d;
  115. 	}
  116. 	printf("%d\n",ans);
  117. 	return 0;
  118. }
Success #stdin #stdout 0s 3532KB
comments (?)
stdin
copy 
5
5
4
3
2
1
1 2
1 3
2 4
2 5
stdout
copy 
3
https://ideone.com/ukYSwU
HNOI2014 米特运输 meat
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!