Advertisement
Guest User

Untitled

a guest
May 7th, 2021
308
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3.  
  4. typedef long long LL;
  5. typedef unsigned long long ULL;
  6. using namespace std;
  7. typedef  vector<int> vi;
  8. typedef  vector<vi> vii;
  9. typedef  vector<tuple<int,int,int>> vti3;
  10.  
  11.  
  12.  
  13. #define FOR(i,a,b) for(int i=a;i<b;i++)
  14. #define pb push_back
  15. #define ll long long
  16. #define pob pop_back
  17. #define si second
  18. #define fi first
  19. #define mii map<int,int>
  20. #define mp make_pair
  21. #define msi map<string,int>
  22. #define musi unorderd_map<string,int>
  23. #define test_n LL N; cin>>N; while(N--)
  24. #define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  25.  #define MAXN 100002
  26.  
  27. vector<int> adj[MAXN];
  28. int depth[MAXN];
  29. vector<int> vertices[MAXN];
  30. int n;
  31.  
  32. inline int dfs(int node){
  33.  
  34. int de=0;
  35.     for(auto u:adj[node]){
  36.        
  37.             de=max(de,dfs(u)+1);
  38.        
  39.     }
  40.  
  41. depth[node]=de;
  42. vertices[de].pb(node);
  43. return de;
  44.  
  45. }
  46.  
  47.  
  48. struct fhash {
  49.     ll operator() (string x) const { return 69; }
  50. };
  51.  
  52. //===============================//
  53. unordered_map<string,int,fhash> oup;
  54. string gof;
  55. int timer=0;
  56. //================================//
  57.  
  58. inline void mera_util(int node,int k){
  59. ++timer;
  60.  
  61. gof.pb('0'+timer); int myt=timer;
  62. if(k==0){ gof.pb('0'+myt); return;}
  63.  
  64.     for(auto u:adj[node]){
  65.         mera_util(u,k-1);
  66.     }
  67.  
  68. gof.pb('0'+myt);
  69.  
  70. }
  71.  
  72. //================================//
  73.  
  74. inline bool mera(int k){
  75. oup.clear();
  76.  
  77.  
  78. vi jog;
  79. FOR(i,k,n){ jog.pb(i);}
  80. random_shuffle(jog.begin(),jog.end());
  81.  
  82.     for(auto i:jog){
  83.     for(auto u:vertices[i]){ timer=0; gof=""; mera_util(u,k);   oup[gof]++; if(oup[gof]>1){return true;}  }
  84.     }
  85.  
  86.  
  87.  
  88. return false;
  89.  
  90. }
  91.  
  92. //================================================//
  93.  
  94. int main(){
  95. fastio;
  96. srand(unsigned(time(0)));
  97. test_n{
  98. cin>>n;
  99. FOR(i,0,n+1){ adj[i].clear(); vertices[i].clear(); }
  100. int chi,a;
  101. FOR(i,1,n+1){
  102.     cin>>chi;
  103.     FOR(j,0,chi){ cin>>a;  adj[i].pb(a); }
  104.    
  105. }
  106.  
  107.  
  108.  
  109. dfs(1);
  110. int ansi=-9;
  111.  
  112. int l=0,r=n-1,mid;
  113.  
  114. while(l<=r){
  115.  
  116. mid=(l+r)/2;
  117.  
  118. if(mera(mid)){ ansi=max(ansi,mid); l=mid+1; }
  119. else{ r=mid-1; }
  120.  
  121. }
  122.  
  123. cout<<ansi<<"\n";
  124.  
  125. }//test_n
  126.  
  127.  
  128.  
  129. return 0;}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement