首页 > 代码库 > XVI Open Cup named after E.V. Pankratiev. GP of SPB

XVI Open Cup named after E.V. Pankratiev. GP of SPB

A. Bubbles

枚举两个点,求出垂直平分线与$x$轴的交点,答案=交点数+1。

时间复杂度$O(n^2\log n)$。

#include<cstdio>#include<algorithm>#include<cmath>using namespace std;const double eps=1e-9;int sgn(double x){  if(x<-eps)return -1;  if(x>eps)return 1;  return 0;}struct P{  double x,y;  P(){x=y=0;}  P(double _x,double _y){x=_x,y=_y;}  P operator+(P v){return P(x+v.x,y+v.y);}  P operator-(P v){return P(x-v.x,y-v.y);}  P operator*(double v){return P(x*v,y*v);}  P operator/(double v){return P(x/v,y/v);}  P rot90(){return P(-y,x);}}a[2000];double q[1111111];double cross(P a,P b){return a.x*b.y-a.y*b.x;}int line_intersection(P a,P b,P p,P q,P&o){  if(!sgn(a.x-b.x)&&!sgn(a.y-b.y))return 0;  if(!sgn(p.x-q.x)&&!sgn(p.y-q.y))return 0;    double U=cross(p-a,q-p),         D=cross(b-a,q-p);  if(sgn(D)==0)return 0;  o=a+(b-a)*(U/D);  return 1;}int main () {  freopen ( "bubbles.in" , "r" , stdin ) ;  freopen ( "bubbles.out" , "w" , stdout ) ;  int n;  scanf("%d",&n);  for(int i=1;i<=n;i++){    scanf("%lf%lf",&a[i].x,&a[i].y);  }  P A(-100,0),B(100,0);  int cnt=0;  for(int i=1;i<=n;i++)for(int j=1;j<i;j++){    P t=(a[i]+a[j])/2.0;    P v=a[i]-a[j];    v=v.rot90();    P tmp;    if(line_intersection(t,t+v,A,B,tmp)){      q[++cnt]=tmp.x;    }  }  sort(q+1,q+cnt+1);  int ans=1;  for(int i=1;i<=cnt;i++)if(i==1||sgn(q[i]-q[i-1]))ans++;  printf("%d",ans);  return 0;}

  

B. Drop7

留坑。

 

C. Eulerian Graphs

留坑。

 

D. At Least Half

枚举所有质数$p$,找出所有$p$的倍数,设$s[i]$表示前$i$个数里$p$的倍数$\times2$,枚举$i$,要找到最小的$j$满足$s[i]-i\geq s[j]-j$,维护$s[i]-i$的前缀最小值,然后二分查找即可。找到$j$之后贪心计算往左往右能扩展多少。

时间复杂度$O(n\log n\log\log n)$。

#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=1000020;int a[Maxn];vector<int>V[Maxn/10];vector<int>pri;int n;bool isp[Maxn];void getp(){	for(int i=2;i<Maxn;i++){		if(!isp[i]){			pri.push_back(i);		}		for(int j=0;j<pri.size();j++){			if(i*pri[j]>=Maxn)break;			isp[i*pri[j]]=1;			if(i%pri[j]==0)break;		}	}}int ans,ansr;int g[Maxn],gmx[Maxn];void check(vector<int>&V){	//for(int i=0;i<V.size();i++)printf("%d ",V[i]);puts("");	for(int i=0;i<V.size();i++)g[i]=V[i]-2*(i+1);	for(int i=0;i<V.size();i++)gmx[i]=V[i]-1-2*(i);	for(int i=1;i<V.size();i++)gmx[i]=max(gmx[i],gmx[i-1]);	for(int i=0;i<V.size();i++){		int j=lower_bound(gmx,gmx+V.size(),g[i])-gmx;		int has=i-j+1,haslen=V[i]-V[j]+1;		//printf("val=1%d val2=%d\n",V[i-1],j);		int rr=i==V.size()-1?n:(V[i+1]-1);		int ll=j==0?1:(V[j-1]+1);		int tmpans=min(rr-ll+1,has*2);		int csr=V[i]+min(tmpans-haslen,rr-V[i]);		//printf("%d %d %d %d\n",ll,rr,has,tmpans);		if(tmpans>ans){			ans=tmpans;			ansr=csr;		}	}}void solve(vector<int>&V){	check(V);}int main(){freopen("halfgcd.in","r",stdin);freopen("halfgcd.out","w",stdout);	getp();	scanf("%d",&n);	for(int i=1;i<=n;i++)scanf("%d",a+i);	for(int i=1;i<=n;i++){		int x=a[i];		for(int j=0;j<pri.size();j++){			if(1LL*pri[j]*pri[j]>x)break;			if(x%pri[j])continue;			V[j].push_back(i);			while(x%pri[j]==0)x/=pri[j];		}		if(x>1)V[lower_bound(pri.begin(),pri.end(),x)-pri.begin()].push_back(i);	}	ans=0,ansr=-1;	for(int it=0;it<pri.size();it++){		if(!V[it].size())continue;		solve(V[it]);	}	if(!ans){		puts("0 0");	}	else printf("%d %d\n",ansr-ans+1,ansr);	return 0;}

  

E. Next Partition in RLE Notation

只有最后几个数是有用的,分类讨论构造即可。

#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;typedef pair < LL , LL > pll ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;vector < pll > G ;int n ;void get ( LL N , LL K , LL val ) {	LL tmp1 = ( N - K ) / ( val - 1 ) ;	LL tmp2 = ( N - K ) % ( val - 1 ) ;	LL tmp3 = K - tmp1 - ( tmp2 > 0 ) ;	if ( tmp1 ) G.push_back ( pll ( tmp1 , val ) ) ;	if ( tmp2 ) G.push_back ( pll ( 1 , tmp2 + 1 ) ) ;	if ( tmp3 ) G.push_back ( pll ( tmp3 , 1 ) ) ;}void solve () {	G.clear () ;	for ( int i = 1 ; i <= n ; ++ i ) {		LL x , y ;		scanf ( "%lld%lld" , &x , &y ) ;		G.push_back ( pll ( x , y ) ) ;	}	if ( n == 1 || n == 2 && G[0].second - G[1].second == 1 ) {		printf ( "-1\n" ) ;		return ;	}	pll a = G[n - 1] ;	-- n ;	G.pop_back () ;	pll b = G[n - 1] ;	if ( G[n - 1].second - a.second > 1 ) {		G[n - 1].first -- ;		if ( !G[n - 1].first ) {			G.pop_back () ;			-- n ;		}		//printf ( "%lld %lld %lld %lld\n" , a.first , a.second , b.first , b.second ) ;		get ( a.first * a.second + b.second , a.first + 1 , b.second - 1 ) ;	} else {		G.pop_back () ;		-- n ;		pll c = G[n - 1] ;		G[n - 1].first -- ;		if ( !G[n - 1].first ) {			G.pop_back () ;			-- n ;		}		get ( a.first * a.second + b.first * b.second + c.second , a.first + b.first + 1 , c.second - 1 ) ;	}	printf ( "%d\n" , ( int ) G.size () ) ;	for ( int i = 0 ; i < G.size () ; ++ i ) {		printf ( "%lld %lld\n" , G[i].first , G[i].second ) ;	}}int main () {	freopen ( "next-partition-rle.in" , "r" , stdin ) ;	freopen ( "next-partition-rle.out" , "w" , stdout ) ;	while ( ~scanf ( "%d" , &n ) ) solve () ;	return 0 ;}

  

F. Equation

留坑。

 

G. “Swap-Plus” Puzzle

显然存在一种最优操作序列,先做行交换,在做列交换,最后再交换格子。

枚举行交换、列交换的顺序,然后贪心交换即可。

#include<cstdio>#include<algorithm>#include<cmath>#include<string>#include<iostream>using namespace std;int i,j,a[9][9],b[9],c[9],d[9][9],m,e[100];int ans=~0U>>1,cnt;string q[100];int now;int cal(int*a,int n){  int t=0;  int i,j;  static int b[100];  for(i=1;i<=n;i++)b[i]=a[i];  for(i=1;i<=n;i++){    for(j=1;j<=n;j++)if(b[j]==i){      if(i!=j)t++;      swap(b[j],b[i]);      break;    }  }  return t;}int cal2(int*a,int n){  int t=0;  int i,j;  static int b[100];  for(i=1;i<=n;i++)b[i]=i;  for(i=1;i<=n;i++){    for(j=1;j<=n;j++)if(b[j]==a[i]){      if(i!=j)t++;      swap(b[j],b[i]);      break;    }  }  return t;}void conb(int*a,char st){//[1,2,3,4]->a  static int b[10];  int i,j;  for(i=1;i<=4;i++)b[i]=i;  for(i=1;i<=4;i++){    for(j=1;j<=4;j++)if(b[j]==a[i]){      if(i!=j){        string t="";        t.push_back(b[i]+st-1);        t.push_back(‘-‘);        t.push_back(b[j]+st-1);        q[++cnt]=t;      }      swap(b[j],b[i]);      break;    }  }}void cond(){//a->[1,2,3,4,...,16]  static int a[9][9];  int i,j,x,y;  for(i=1;i<=4;i++)for(j=1;j<=4;j++)a[i][j]=d[i][j];  for(i=1;i<=4;i++)for(j=1;j<=4;j++){    int now=(i-1)*4+j;    if(a[i][j]==now)continue;    bool flag=0;    for(x=1;x<=4;x++){      for(y=1;y<=4;y++)if(a[x][y]==now){        flag=1;        swap(a[x][y],a[i][j]);        string t="";        t.push_back(i+‘a‘-1);        t.push_back(j+‘0‘);        t.push_back(‘-‘);        t.push_back(x+‘a‘-1);        t.push_back(y+‘0‘);        q[++cnt]=t;        break;      }      if(flag)break;    }  }}int main (){  freopen ( "puzzle-swap-plus.in" , "r" , stdin ) ;  freopen ( "puzzle-swap-plus.out" , "w" , stdout ) ;  for(i=1;i<=4;i++)    for(j=1;j<=4;j++)      scanf("%d",&a[i][j]);  for(i=1;i<=4;i++)b[i]=i;    do{    for(i=1;i<=4;i++)c[i]=i;    do{      now=cal2(b,4)+cal2(c,4);      for(i=1;i<=4;i++)for(j=1;j<=4;j++)d[b[i]][c[j]]=a[i][j];      m=0;      for(i=1;i<=4;i++)for(j=1;j<=4;j++)e[++m]=d[i][j];      now+=cal(e,16);      if(now<ans){        ans=now;        cnt=0;        conb(b,‘a‘);        conb(c,‘1‘);        cond();      }    }while(next_permutation(c+1,c+4+1));  }while(next_permutation(b+1,b+4+1));  printf("%d\n",ans);  for(i=1;i<=cnt;i++)cout<<q[i]<<endl;  return 0;}

  

H. Wrong Sieve

考虑每一轮与上一轮位置的递推关系即可。

#include<bits/stdc++.h>using namespace std;const int Maxn=105;typedef long long LL;typedef pair<int,int>pi;LL solve(LL x){	for(LL i=1;x>=(i+1);i++){		if(x%(i+1)==0)return -1;		x=x-x/(i+1);	}	return x;}int main(){freopen("sieve.in","r",stdin);freopen("sieve.out","w",stdout);	int _;scanf("%d",&_);	while(_--){		LL x;scanf("%lld",&x);		LL ans=solve(x);		printf("%lld\n",ans);	}	return 0;}

  

I. Space Cat

DP,$f[i][j]$表示在第$i$条线段,重心方向为$j$的最小代价,注意要特判图不联通的情况。

时间复杂度$O(n)$。

#include <bits/stdc++.h>using namespace std ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )typedef long long ll;const ll inf=1LL<<60;const int N=100010;int n,i,a[N],b[N],c[N];ll f[N][2];inline void up(ll&x,ll y){if(x>y)x=y;}int main () {	int T ;	freopen ( "space-cat.in" , "r" , stdin ) ;	freopen ( "space-cat.out" , "w" , stdout ) ;	scanf("%d",&n);	for(i=1;i<=n;i++)scanf("%d",&a[i]);	for(i=1;i<=n;i++)scanf("%d",&b[i]),c[i]=a[i]-b[i];	for(i=2;i<=n;i++)if(b[i]>=a[i-1]||b[i-1]>=a[i])return puts("-1"),0;	for(i=1;i<=n;i++)f[i][0]=f[i][1]=inf;	f[1][0]=0;	for(i=1;i<=n;i++){	  if(i>1){	    if(a[i-1]<=a[i])up(f[i][1],f[i-1][1]);	    if(b[i-1]>=b[i])up(f[i][0],f[i-1][0]);          }          for(int j=0;j<4;j++){            up(f[i][0],f[i][1]+c[i]);            up(f[i][1],f[i][0]+c[i]);          }	}	if(f[n][0]>=inf)f[n][0]=-1;	printf("%lld\n",f[n][0]);	return 0 ;}

  

J. Tic-Tac-Toe Variation

第一步填中间,然后只有两种情况,分类讨论构造策略即可。

#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=1000020;char Mp[4][4];bool getMp(){	bool ret=0;	for(int i=0;i<3;i++){		scanf("%s",Mp[i]);		for(int j=0;j<3;j++){			if(Mp[i][j]!=‘x‘)ret=1;		}	}	return ret;}int idx[3][3]={	{0,1,2},	{7,-1,3},	{6,5,4}};int dx[8],dy[8];int curMp[3][3];int cg(char c){	if(c==‘.‘)return 0;	if(c==‘x‘)return 1;	return 2;}void tran(){	for(int i=0;i<3;i++){		for(int j=0;j<3;j++){			curMp[i][j]=cg(Mp[i][j]);		}	}}void pt(){	for(int i=0;i<3;i++){		for(int j=0;j<3;j++){			int c=curMp[i][j];			if(!c)putchar(‘.‘);			if(c==1)putchar(‘x‘);			if(c==2)putchar(‘o‘);		}		puts("");	}	fflush(stdout);}int getst(){	for(int i=0;i<3;i++){		for(int j=0;j<3;j++){			if(curMp[i][j]==2){				return idx[i][j];			}		}	}}int main(){//freopen("halfgcd.in","r",stdin);//freopen("halfgcd.out","w",stdout);	for(int i=0;i<3;i++){		for(int j=0;j<3;j++){			if(i==1&&j==1)continue;			dx[idx[i][j]]=i;			dy[idx[i][j]]=j;		}	}	while(getMp()){		int st;		memset(curMp,0,sizeof curMp);		for(int it=0;;it++){			if(it==0){				curMp[1][1]=1;				pt();				continue;			}			if(it==1){				getMp();				tran();				st=getst();				int nst=(st+2)%8;				curMp[dx[nst]][dy[nst]]=1;				pt();				continue;			}			if(it==2){				getMp();				tran();				if(curMp[dx[(st+6)%8]][dy[(st+6)%8]]!=2){					curMp[dx[(st+6)%8]][dy[(st+6)%8]]=1;					pt();					break;				}				else{					curMp[dx[(st+3)%8]][dy[(st+3)%8]]=1;					pt();				}			}			if(it==3){				getMp();				tran();				int nst=st&1?((st+1)%8):((st+4)%8);				if(!curMp[dx[nst]][dy[nst]]){					curMp[dx[nst]][dy[nst]]=1;					pt();					break;				}				else{					nst=(st+7)%8;					curMp[dx[nst]][dy[nst]]=1;					pt();					break;				}			}		}	}	return 0;}

  

K. Captain Tarjan

对于每个询问,将路径上的边权都加1。

那么问题就变成了,给定一棵树,找到一个点,然后随意剖分,使得所有轻边的权值和最小,两遍DP即可。

时间复杂度$O(m\log n)$。

#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;vector < pii > G[MAXN] ;LL dp[MAXN] , dp2[MAXN] , maxc[MAXN] ;LL Ldp[MAXN] , Rdp[MAXN] , Lmaxc[MAXN] , Rmaxc[MAXN] ;int c[MAXN] ;int siz[MAXN] ;int son[MAXN] ;int pre[MAXN] ;int top[MAXN] ;int dep[MAXN] ;int n , m ;LL ans ;void predfs ( int u , int f ) {	siz[u] = 1 ;	son[u] = 0 ;	for ( int i = 0 ; i < G[u].size () ; ++ i ) {		int v = G[u][i].first ;		if ( v == f ) continue ;		pre[v] = u ;		dep[v] = dep[u] + 1 ;		predfs ( v , u ) ;		siz[u] += siz[v] ;		if ( siz[v] > siz[son[u]] ) son[u] = v ;	}}void rebuild ( int u , int top_element ) {	top[u] = top_element ;	if ( son[u] ) rebuild ( son[u] , top_element ) ;	for ( int i = 0 ; i < G[u].size () ; ++ i ) {		int v = G[u][i].first ;		if ( v != pre[u] && v != son[u] ) rebuild ( v , v ) ;	}}int get_lca ( int x , int y ) {	while ( top[x] != top[y] ) {		if ( dep[top[x]] > dep[top[y]] ) x = pre[top[x]] ;		else y = pre[top[y]] ;	}	return dep[x] < dep[y] ? x : y ;}void dfs1 ( int u ) {	for ( int i = 0 ; i < G[u].size () ; ++ i ) {		int v = G[u][i].first ;		if ( v == pre[u] ) continue ;		dfs1 ( v ) ;		G[u][i].second = c[v] ;		c[u] += c[v] ;	}}void dfs2 ( int u ) {	dp[u] = maxc[u] = 0 ;	for ( int i = 0 ; i < G[u].size () ; ++ i ) {		int v = G[u][i].first ;		if ( v == pre[u] ) continue ;		dfs2 ( v ) ;		dp[u] += dp[v] + G[u][i].second ;		maxc[u] = max ( maxc[u] , G[u][i].second + 0LL ) ;	}	dp[u] -= maxc[u] ;}void dfs3 ( int u , int cost ) {	int n = G[u].size () ;	Ldp[0] = 0 ;	Rdp[n - 1] = 0 ;	Lmaxc[0] = 0 ;	Rmaxc[n - 1] = 0 ;	for ( int i = 1 ; i < n ; ++ i ) {		int v = G[u][i - 1].first ;		if ( v == pre[u] ) {			Ldp[i] = Ldp[i - 1] ;			Lmaxc[i] = Lmaxc[i - 1] ;		} else {			Ldp[i] = Ldp[i - 1] + dp[v] + G[u][i - 1].second ;			Lmaxc[i] = max ( Lmaxc[i - 1] , G[u][i - 1].second + 0LL ) ;		}	}	for ( int i = n - 2 ; i >= 0 ; -- i ) {		int v = G[u][i + 1].first ;		if ( v == pre[u] ) {			Rdp[i] = Rdp[i + 1] ;			Rmaxc[i] = Rmaxc[i + 1] ;		} else {			Rdp[i] = Rdp[i + 1] + dp[v] + G[u][i + 1].second ;			Rmaxc[i] = max ( Rmaxc[i + 1] , G[u][i + 1].second + 0LL ) ;		}	}	for ( int i = 0 ; i < n ; ++ i ) {		int v = G[u][i].first ;		if ( v == pre[u] ) continue ;		dp2[v] = dp2[u] + Ldp[i] + Rdp[i] + cost - max ( max ( Lmaxc[i] , Rmaxc[i] ) , cost + 0LL ) ;		ans = min ( ans , dp2[v] + dp[v] + maxc[v] + G[u][i].second - max ( maxc[v] , 0LL + G[u][i].second ) ) ;	}	for ( int i = 0 ; i < n ; ++ i ) {		int v = G[u][i].first ;		if ( v == pre[u] ) continue ;		dfs3 ( v , G[u][i].second ) ;	}}void solve () {	for ( int i = 1 ; i <= n ; ++ i ) {		G[i].clear () ;		c[i] = 0 ;	}	for ( int i = 1 ; i < n ; ++ i ) {		int u , v ;		scanf ( "%d%d" , &u , &v ) ;		G[u].push_back ( pii ( v , 0 ) ) ;		G[v].push_back ( pii ( u , 0 ) ) ;	}	predfs ( 1 , 1 ) ;	rebuild ( 1 , 1 ) ;	for ( int i = 0 ; i < m ; ++ i ) {		int u , v ;		scanf ( "%d%d" , &u , &v ) ;		c[u] ++ ;		c[v] ++ ;		int lca = get_lca ( u , v ) ;		c[lca] -= 2 ;	}	dp2[1] = 0 ;	dfs1 ( 1 ) ;	dfs2 ( 1 ) ;	ans = dp[1] ;	dfs3 ( 1 , 0 ) ;	printf ( "%lld\n" , ans ) ;}int main () {	freopen ( "treepaths.in" , "r" , stdin ) ;	freopen ( "treepaths.out" , "w" , stdout ) ;	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;	return 0 ;}

  

L. Gardening Lesson

求出两棵树的重心,枚举重心作为根,然后求出每棵子树的Hash值,在两棵树上一起dfs即可。

时间复杂度$O(n\log n)$。

#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn = 100005 , x = 123 , M = 998244353 , Left = 23 , Right = 371 ;const int Hleaf=Left*Right,Inf=1e9;vector < int > G1[Maxn] , G2[Maxn] ;int H1[Maxn] , H2[Maxn] ;int sz[Maxn],sonsz[Maxn],ans ;void dfs(int u , vector<int>*G,int p){	sz[u]= 1;	sonsz[u]=0;	for(int i=0;i<G[u].size ();++i){		int v =G[u][i];		if(v==p)continue ;		dfs(v,G,u);		sz[u]+=sz[v];		if(sz[v]>sonsz[u])sonsz[u]=sz[v];	}}vector<int>getroot(vector<int>*G,int n){	dfs(1,G,0);	vector<int>ret;	for(int i=1;i<=n;++i){		if(max(n-sz[i],sonsz[i])<=n/2){			ret.push_back(i);		}	}	return ret;}bool cmp1(int a, int b){return H1[a]<H1[b];}bool cmp2(int a, int b){return H2[a]<H2[b];}void dfs2(int u,int p,vector<int>*G,int*H,int ty){	H[u]=Left;	for(int i =0;i<G[u].size();++i){		int v=G[u][i];if(v==p)continue;		dfs2(v,u,G,H,ty);	}	sort(G[u].begin(),G[u].end(),ty==1?cmp1:cmp2);	for(int i=0;i<G[u].size();++i){		int v=G[u][i];if(v==p)continue;		H[u]=((1LL*H[u]*x)^H[v])%M;	}	H[u]=1LL*H[u]*Right%M;}void check(int ua,int pa,int ub,int pb){	//printf("%d %d %d %d\n",ua,pa,ub,pb);	set<pi>S;	for(int i=0;i<G2[ub].size();i++){		int v=G2[ub][i];		if(v==pb)continue;		S.insert(pi(H2[v],v));	}	vector<int>rest;	for(int i=0;i<G1[ua].size();i++){		int v=G1[ua][i];		if(v==pa)continue;		set<pi>::iterator it=S.lower_bound(pi(H1[v],-1));		if(it==S.end()||(it->first!=H1[v]))rest.push_back(v);		else S.erase(it);	}	if(rest.size()>1||S.size()>1)return;	if(S.size()==1&&!rest.size()){		if(S.begin()->first!=Hleaf)return;		for(int i=0;i<G2[ub].size();i++){			int v=G2[ub][i];if(v==pb)continue;			if(H2[v]==Hleaf){ans=min(ans,v);}		}		return;	}	if(S.size()==1&&rest.size()==1){		for(int i=0;i<G2[ub].size();i++){			int v=G2[ub][i];if(v==pb)continue;			if(H2[v]==S.begin()->first)check(rest[0],ua,v,ub);		}	}}void solve( int rt1 , int rt2){	dfs2(rt1,0,G1,H1,1);	dfs2(rt2,0,G2,H2,2);	check(rt1,0,rt2,0);}void pt(vector<int>&v){	for(int i=0;i<v.size();i++)printf("%d ",v[i]);	puts("");}int main(){freopen("unexpected-leaf.in","r",stdin);freopen("unexpected-leaf.out","w",stdout);	int n;	while(scanf("%d",&n)!=EOF){		for(int i=1;i<=n+1;i++){			G1[i].clear();			G2[i].clear();		}		for(int i=1;i<n;i++){			int u,v;scanf("%d%d",&u,&v);			G1[u].push_back(v);			G1[v].push_back(u);		}		for(int i=1;i<=n;i++){			int u,v;scanf("%d%d",&u,&v);			G2[u].push_back(v);			G2[v].push_back(u);		}		if(n==1){			printf("1\n");			continue;		}		if(n==2){			if(G2[1].size()==2)printf("2\n");			else printf("1\n");			continue;		}		vector<int>tmp1=getroot(G1,n);		vector<int>tmp2=getroot(G2,n+1);		//pt(tmp1);		//pt(tmp2);		ans=Inf;		//solve(1,3);		for(int i=0;i<tmp1.size();i++){			for(int j=0;j<tmp2.size();j++){				solve(tmp1[i],tmp2[j]);			}		}		printf("%d\n",ans);	}	return 0;}

  


总结:

  • L题发现树同构模板有误。

 

XVI Open Cup named after E.V. Pankratiev. GP of SPB