nicuvlad76

Untitled

Feb 26th, 2023
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.48 KB | None | 0 0
  1. /*
  2. Paul Diac
  3. solutile problema smallworld
  4. memorie: O(N)
  5. timp: O(N)
  6. idee: doua parcurgeri DFS/BFS din radacina aleasa nodul 1, in care calculez:
  7. hmax[i] = distanta maxima din subarborele i de la i pana la orice frunza
  8. = 1 + maximul dintre hmax[] din fii
  9. dtop[i] = distanta maxima plecand din i in sus macar o muchie si apoi eventual in jos
  10. = max(dtop[parinte(i)] + 1, max(hmax[frate(i)]) - pentru orice frate/sibling)
  11. */
  12. #include <stdio.h>
  13. #include <vector>
  14. #include <algorithm>
  15. #define NMax 100005
  16.  
  17. using namespace std;
  18.  
  19. int N;
  20. vector<int> p[NMax]; // p[i] = prieteni lui i
  21. int viz[NMax], t[NMax]; // t[i] = tatal lui i
  22.  
  23. int hmax[NMax]; // distanta maxima "in jos"
  24. int dtop[NMax]; // distanta maxima "in sus" (si apoi eventual in jos)
  25. int phm[NMax][2]; // hm[i] = cei doi prietenii-fii ai lui i care au hmax[] cel mai mare
  26.  
  27. void DFS_hmax(int a) {
  28. for (int i = 0; i < p[a].size(); i++) {
  29. if (!viz[p[a][i]]) {
  30. viz[p[a][i]] = 1;
  31. DFS_hmax(p[a][i]);
  32. t[p[a][i]] = a;
  33. }
  34. }
  35. for (int i = 0; i < p[a].size(); i++) {
  36. if (hmax[a] < hmax[p[a][i]] + 1) {
  37. hmax[a] = hmax[p[a][i]] + 1;
  38. }
  39. }
  40.  
  41. }
  42. void DFS_dtop(int a) {
  43. if (t[a]) {
  44. if (dtop[a] < dtop[t[a]] + 1) { dtop[a] = dtop[t[a]] + 1; }
  45. // evit un worst case O(N^2) - atunci cand a are foarte multi frati
  46. // folosesc cei doi fii ai tatalui cu hmax[] maxim pre-calculati
  47. // este nevoie de doi pentru ca unul ar putea fi chiar a
  48. for (int j = 0; j < 2; j++) {
  49. int s = phm[t[a]][j];
  50. if (s != 0 && s != a && dtop[a] < hmax[s] + 2) { dtop[a] = hmax[s] + 2; }
  51. }
  52. }
  53. for (int i = 0; i < p[a].size(); i++) {
  54. if (!viz[p[a][i]]) {
  55. viz[p[a][i]] = 1;
  56. DFS_dtop(p[a][i]);
  57. }
  58. }
  59. }
  60.  
  61. int main() {
  62. freopen("smallworld.in", "r", stdin);
  63. freopen("smallworld.out", "w", stdout);
  64. scanf("%d", &N);
  65. int a, b, dMax;
  66. for (int i = 0; i < N-1; i++) {
  67. scanf("%d %d", &a, &b);
  68. p[a].push_back(b);
  69. p[b].push_back(a);
  70. }
  71. viz[1] = 1;
  72. DFS_hmax(1);
  73.  
  74. for (int i = 1; i <= N; i++) {
  75. hmax[i]--;
  76. viz[i] = 0;
  77. }
  78.  
  79. for (int i = 1; i <= N; i++) {
  80. if (phm[t[i]][0] == 0 || hmax[phm[t[i]][0]] < hmax[i]) {
  81. phm[t[i]][1] = phm[t[i]][0];
  82. phm[t[i]][0] = i;
  83. } else if (phm[t[i]][1] == 0 || hmax[phm[t[i]][1]] < hmax[i]) {
  84. phm[t[i]][1] = i;
  85. }
  86. }
  87.  
  88. DFS_dtop(1);
  89. dMax = 0;
  90.  
  91. for (int i = 1; i <= N; i++) {
  92. if (hmax[i] < dtop[i]) {
  93. printf("%ld\n", dtop[i]);
  94. } else {
  95. printf("%ld\n", hmax[i]);
  96. }
  97. }
  98. return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment