1 条题解

  • 0
    @ 2023-6-21 20:04:21

    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

    #6066. 「2017 山东一轮集训 Day3」第二题

    信息

    ID
    1028
    时间
    2000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者