1 条题解
-
0
C++ :
#include <cstdio> struct Istream { template <class T> Istream &operator >>(T &x) { static char ch;static bool neg; for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar()); for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar()); x=neg?-x:x; return *this; } }is; struct Ostream { template <class T> Ostream &operator <<(T x) { x<0 && (putchar('-'),x=-x); static char stack[233];static int top; for(top=0;x;stack[++top]=x%10+'0',x/=10); for(top==0 && (stack[top=1]='0');top;putchar(stack[top--])); return *this; } Ostream &operator <<(char ch) { putchar(ch); return *this; } }os; #include <set> #include <vector> #define int64 long long const int MAXN=100000+11; template <class T> inline bool chkmx(T &a,T const &b) { return a<b?a=b,1:0; } std::vector<int> son[MAXN]; int lbr[MAXN],rbr[MAXN],brc,bra[MAXN<<1],longCh[MAXN]; void PreDFS(int pos) { bra[++brc]=0; lbr[pos]=brc; longCh[pos]=1; for(int &u:son[pos]) { PreDFS(u); chkmx(longCh[pos],longCh[u]+1); } bra[++brc]=1; rbr[pos]=brc; } int n,kDist; std::vector<int> kSon[MAXN]; void GetKSon(int pos) { static int stack[MAXN],top; stack[++top]=pos; if(top>kDist+1) { kSon[stack[top-kDist-1]].push_back(pos); } for(int &u:son[pos]) { GetKSon(u); } top--; } typedef unsigned int64 Hash; const Hash LBR=3,RBR=4,BASE=5; Hash pHash[MAXN<<1],powBASE[MAXN<<1]; Hash SubStr(int l,int r) { return pHash[r]-pHash[l-1]*powBASE[r-l+1]; } std::set<Hash> S; bool Exist(int K) { kDist=K; for(int i=1;i<=n;++i) { kSon[i].clear(); } S.clear(); GetKSon(1); for(int pos=1;pos<=n;++pos) if(longCh[pos]>=kDist+1) {//kDist+1!!!!!!! !! !! int l=lbr[pos],r=rbr[pos]; Hash hc=0; for(int &u:kSon[pos]) { r=lbr[u]-1; if(l<=r) { (hc*=powBASE[r-l+1])+=SubStr(l,r); } l=rbr[u]+1; r=rbr[pos]; } if(l<=r) { (hc*=powBASE[r-l+1])+=SubStr(l,r); } if(!S.count(hc)) { S.insert(hc); } else { return 1; } } return 0; } int main() { is>>n; for(int i=1;i<=n;++i) { int cnt;is>>cnt; son[i].resize(cnt); for(int j=0;j<cnt;++j) { is>>son[i][j]; } } PreDFS(1); powBASE[0]=1; for(int i=1;i<=brc;++i) { pHash[i]=pHash[i-1]*BASE+(bra[i]==0?LBR:RBR); powBASE[i]=powBASE[i-1]*BASE; } int L=0,R=n-1; while(L!=R) { int M=(L+R+1)>>1; if(Exist(M)) { L=M; } else { R=M-1; } } os<<L<<'\n'; return 0; }
- 1
信息
- ID
- 1028
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者