Submission #2242946


Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int N=200005;
const int LGN=18;
const int E=N<<1;

struct tree
{
	int tov[E],nxt[E];
	int last[N];
	int tot;

	inline void insert(int x,int y){tov[++tot]=y,nxt[tot]=last[x],last[x]=tot;}
}t[2];

int LOG[N],depth[N];
int anc[N][LGN];
int n,srcx,srcy,ans;

void dfs(int x)
{
	for (int i=t[1].last[x],y;i;i=t[1].nxt[i])
		if ((y=t[1].tov[i])!=anc[x][0]) depth[y]=depth[anc[y][0]=x]+1,dfs(y);
}

void pre()
{
	LOG[1]=0;
	for (int i=2;i<=n;++i) LOG[i]=LOG[i-1]+(1<<LOG[i-1]+1==i);
	for (int i=1;i<=LOG[n];++i)
		for (int x=1;x<=n;++x)
			anc[x][i]=anc[anc[x][i-1]][i-1];
}

inline int adjust(int x,int h)
{
	for (int i=LOG[depth[x]];i>=0;--i) if (depth[anc[x][i]]>=h) x=anc[x][i];
	return x;
}

inline int lca(int x,int y)
{
	if (depth[x]>depth[y]) swap(x,y);
	y=adjust(y,depth[x]);
	if (x==y) return x;
	for (int i=LOG[depth[x]];i>=0;--i) if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}

inline int dist(int x,int y){return depth[x]+depth[y]-(depth[lca(x,y)]<<1);}

void calc(int x,int fa=0,int cur=0)
{
	if (cur>=depth[x]-1) return;
	ans=max(ans,depth[x]-1<<1);
	for (int i=t[0].last[x],y;~ans&&i;i=t[0].nxt[i])
		if ((y=t[0].tov[i])!=fa)
		{
			if (dist(x,y)>2) ans=-1;
			else calc(y,x,cur+1);
		}
}

int main()
{
	//freopen("sugigma.in","r",stdin),freopen("sugigma.out","w",stdout);
	n=read(),srcx=read(),srcy=read();
	for (int s=0;s<2;++s)
		for (int i=1,x,y;i<n;++i)
			x=read(),y=read(),t[s].insert(x,y),t[s].insert(y,x);
	depth[srcy]=1,dfs(srcy),pre(),ans=0,calc(srcx);
	printf("%d\n",ans);
	//fclose(stdin),fclose(stdout);
	return 0;
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User crazy_cloud
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 1928 Byte
Status AC
Exec Time 127 ms
Memory 32128 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 5
AC × 103
Set Name Test Cases
Sample example0, example1, example2, example3, example4
All doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, doublestar5, doublestar6, doublestar7, example0, example1, example2, example3, example4, giri0, giri1, giri2, giri3, giri4, giri5, giri6, giri7, giri8, giri9, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, narashi0, narashi1, narashi2, narashi3, narashi4, narashi5, narashi6, narashi7, narashi8, narashi9, ok0, ok1, ok2, ok3, ok4, ok5, ok6, ok7, ok8, ok9, ouh0, ouh1, ouh2, ouh3, ouh4, ouh5, ouh6, ouh7, ouh8, ouh9, same0, same1, same2, same3, same4, same5, same6, same7, same8, same9, sameline0, sameline1, sameline2, sameline3, sameline4, sameline5, sameline6, sameline7, sameline8, sameline9, star0, star1, star2, star3, star4, star5, star6, star7, star8, star9, supersmall0, supersmall1, supersmall2, supersmall3, supersmall4, supersmall5, supersmall6, supersmall7, supersmall8, supersmall9
Case Name Status Exec Time Memory
doublestar0 AC 66 ms 23680 KB
doublestar1 AC 62 ms 23552 KB
doublestar2 AC 64 ms 23552 KB
doublestar3 AC 62 ms 23424 KB
doublestar4 AC 68 ms 23680 KB
doublestar5 AC 69 ms 23680 KB
doublestar6 AC 63 ms 23552 KB
doublestar7 AC 61 ms 23552 KB
example0 AC 3 ms 10496 KB
example1 AC 3 ms 10496 KB
example2 AC 3 ms 10496 KB
example3 AC 3 ms 10496 KB
example4 AC 3 ms 10496 KB
giri0 AC 80 ms 23680 KB
giri1 AC 85 ms 23680 KB
giri2 AC 84 ms 23680 KB
giri3 AC 85 ms 23680 KB
giri4 AC 86 ms 23680 KB
giri5 AC 88 ms 23680 KB
giri6 AC 90 ms 23680 KB
giri7 AC 84 ms 23680 KB
giri8 AC 84 ms 23680 KB
giri9 AC 82 ms 23808 KB
maxrand0 AC 71 ms 23680 KB
maxrand1 AC 71 ms 23680 KB
maxrand2 AC 71 ms 23680 KB
maxrand3 AC 69 ms 23680 KB
maxrand4 AC 69 ms 23552 KB
maxrand5 AC 67 ms 23552 KB
maxrand6 AC 69 ms 23552 KB
maxrand7 AC 71 ms 23680 KB
maxrand8 AC 69 ms 23552 KB
maxrand9 AC 69 ms 23680 KB
narashi0 AC 84 ms 23552 KB
narashi1 AC 83 ms 23680 KB
narashi2 AC 82 ms 23552 KB
narashi3 AC 83 ms 23680 KB
narashi4 AC 90 ms 23680 KB
narashi5 AC 84 ms 23680 KB
narashi6 AC 88 ms 23680 KB
narashi7 AC 86 ms 23680 KB
narashi8 AC 87 ms 23680 KB
narashi9 AC 86 ms 23680 KB
ok0 AC 109 ms 30976 KB
ok1 AC 107 ms 32000 KB
ok2 AC 98 ms 28928 KB
ok3 AC 108 ms 32128 KB
ok4 AC 109 ms 27136 KB
ok5 AC 95 ms 28672 KB
ok6 AC 112 ms 29568 KB
ok7 AC 86 ms 27136 KB
ok8 AC 100 ms 30464 KB
ok9 AC 104 ms 29952 KB
ouh0 AC 78 ms 24192 KB
ouh1 AC 81 ms 25088 KB
ouh2 AC 83 ms 26496 KB
ouh3 AC 87 ms 26496 KB
ouh4 AC 88 ms 25856 KB
ouh5 AC 98 ms 30208 KB
ouh6 AC 96 ms 31104 KB
ouh7 AC 84 ms 25472 KB
ouh8 AC 96 ms 29312 KB
ouh9 AC 96 ms 31104 KB
same0 AC 82 ms 23680 KB
same1 AC 81 ms 23680 KB
same2 AC 71 ms 23680 KB
same3 AC 71 ms 23680 KB
same4 AC 72 ms 23552 KB
same5 AC 81 ms 23552 KB
same6 AC 73 ms 23680 KB
same7 AC 82 ms 23552 KB
same8 AC 68 ms 23552 KB
same9 AC 88 ms 23680 KB
sameline0 AC 112 ms 31616 KB
sameline1 AC 127 ms 31744 KB
sameline2 AC 98 ms 29568 KB
sameline3 AC 105 ms 30592 KB
sameline4 AC 101 ms 31360 KB
sameline5 AC 120 ms 31360 KB
sameline6 AC 95 ms 28672 KB
sameline7 AC 124 ms 30976 KB
sameline8 AC 100 ms 29824 KB
sameline9 AC 107 ms 28544 KB
star0 AC 67 ms 23552 KB
star1 AC 67 ms 23552 KB
star2 AC 63 ms 23552 KB
star3 AC 67 ms 23680 KB
star4 AC 69 ms 23680 KB
star5 AC 72 ms 23680 KB
star6 AC 65 ms 23680 KB
star7 AC 67 ms 23552 KB
star8 AC 69 ms 23552 KB
star9 AC 71 ms 23680 KB
supersmall0 AC 3 ms 10496 KB
supersmall1 AC 3 ms 10496 KB
supersmall2 AC 3 ms 10496 KB
supersmall3 AC 3 ms 10496 KB
supersmall4 AC 3 ms 10496 KB
supersmall5 AC 3 ms 10496 KB
supersmall6 AC 3 ms 10496 KB
supersmall7 AC 3 ms 10496 KB
supersmall8 AC 3 ms 10496 KB
supersmall9 AC 3 ms 10496 KB