fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define snuke(i,x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i)
  3. #define out(x) std::cout<<(#x)<<":"<<(x)<<std::endl
  4. void Read(int&ret){ret=0;bool ok=0,u=0;for(;;){int c=getchar();if(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',ok=1;else if(c=='-')u=1;else if(ok){if(u)ret*=-1;return;}}}
  5. long long pow_mod(long long p,int n,long long mod){long long ret=1;for(;n;n>>=1){if(n&1)ret=ret*p%mod;p=p*p%mod;}return ret;}
  6. /****head****/
  7. const int Max_N = 9 + (int)2e5;
  8. const int Max_M = 21;
  9. int fa[Max_N], q[Max_N], n;
  10. int f[Max_N][Max_M], g[Max_N][Max_M];
  11. std::vector<int> son[Max_N];
  12. void bfs() {
  13.         int qr = 0; q[qr++] = 0;
  14.         for(int i = 0, x; i < qr; ++i) {
  15.                 x = q[i];
  16.                 snuke(it, son[x]) if(*it != fa[x]){
  17.                         q[qr++] = *it;
  18.                 }
  19.         }
  20.         for(int i = qr-1, x, j, fir, sec; i >= 0; --i) {
  21.                 x = q[i];
  22.                 if(son[x].empty()) for(j = 1; j < Max_M; ++j) f[x][j] = j;
  23.                 else {
  24.                         for(j = 1; j < Max_M; ++j) {
  25.                                 f[x][j] = j;
  26.                                 snuke(it, son[x]) f[x][j] += g[*it][j];
  27.                         }
  28.                 }
  29.  
  30.                 sec = 0; fir = 1;
  31.                 for(j = 2; j < Max_M; ++j) {
  32.                         if(f[x][j] >= f[x][fir]) {
  33.                                 if(!sec || f[x][sec] > f[x][j]) sec = j;
  34.                         } else {
  35.                                 sec = fir; fir = j;
  36.                         }
  37.                 }
  38.  
  39.                 for(j = 1; j < Max_M; ++j) g[x][j] = j == fir ? f[x][sec] : f[x][fir];
  40.         }
  41. }
  42. int main() {
  43.         freopen("corporate_gifting.txt","r",stdin);
  44.         freopen("D.out","w",stdout);
  45.         int _; Read(_);
  46.         for(int cas = 0, ans; _--; ) {
  47.                 Read(n);
  48.                 for(int i = 0; i < n; ++i) son[i].clear();
  49.                 for(int i = 0; i < n; ++i) {
  50.                         Read(fa[i]);
  51.                         son[--fa[i]].push_back(i);
  52.                 }
  53.                 bfs();
  54.                 ans = ~0u>>1;
  55.                 for(int i = 1; i < Max_M; ++i) ans = std::min(ans, f[0][i]);
  56.                 printf("Case #%d: %d\n", ++cas, ans);
  57.         }
  58.         return 0;
  59. }
  60.  
Time limit exceeded #stdin #stdout 5s 39864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/m6WZAd
language:
C++14 (gcc 8.3)
created:
9 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!