fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <cctype>
  20. #include <string>
  21. #include <cstring>
  22. #include <cstdio>
  23. #include <cmath>
  24. #include <cstdlib>
  25. #include <ctime>
  26. #include <string.h>
  27. #include <fstream>
  28. #include <cassert>
  29. using namespace std;
  30.  
  31. #define sz(a) int((a).size())
  32. #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
  33. #define rev(i, n, s)  for(int i = (n); i >= s; --i)
  34. #define fore(x, a) for(auto &&x : a)
  35. typedef long long ll;
  36. const int mod = 1000000007;
  37. const int N = 1005;
  38.  
  39. vector<int> g[N];
  40. int d[N][N];
  41.  
  42. void go(int x, int p, int c, int _depth) {
  43.   d[c][_depth]++;
  44.   fore(y, g[x]) {
  45.     if (y == p) continue;
  46.     go(y, x, c, _depth + 1);
  47.   }
  48. }
  49.  
  50. class TreeDiameters {
  51. public:
  52.   int getMax( vector <int> p ) {
  53.     int ans = 0;
  54.     int n = sz(p) + 1;
  55.     rep(i, 0, n - 1) {
  56.       g[i].clear();
  57.     }
  58.     rep(i, 0, n - 2) {
  59.       g[p[i]].push_back(i + 1);
  60.       g[i + 1].push_back(p[i]);
  61.     }
  62.     rep(i, 0, n - 1) {
  63.       int m = sz(g[i]) - 1;
  64.       rep(j, 0, m) {
  65.         memset(d[j], 0, sizeof(d[j]));
  66.       }
  67.       rep(j, 0, m) {
  68.         go(g[i][j], i, j, 0);
  69.       }
  70.       rep(j, 0, n - 1) {
  71.         int tot = 0;
  72.         rep(k, 0, m) {
  73.           tot += d[k][j];
  74.         }
  75.         if (tot == 0) break;
  76.         int cur = 0;
  77.         rep(k, 0, m) {
  78.           cur += d[k][j] * (tot - d[k][j]);
  79.         }
  80.         ans = max(ans, cur/2);
  81.       }
  82.     }
  83.     rep(i, 0, n - 2) {
  84.       rep(j, 0, 1) memset(d[j], 0, sizeof(d[j]));
  85.       go(i + 1, p[i], 0, 0);
  86.       go(p[i], i + 1, 1, 0);
  87.       rep(j, 0, n - 1) {
  88.         if (d[0][j] == 0 && d[1][j] == 0) break;
  89.         ans = max(ans, d[0][j] * d[1][j]);
  90.       }
  91.     }
  92.     return ans;
  93.   }
  94. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/1woxtj
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!