Submission #1694430


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=2e5+5;
int n,X,Y,tot;
int a[maxn],b[maxn],dep[maxn],fa[maxn][20];
int head[maxn],des[maxn<<1],nxt[maxn<<1];
int mark[maxn],q[maxn],mint[maxn],vis[maxn];
vector<int>e[maxn];
void adde(int x,int y){
	des[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
void dfs(int x){
	Rep(p,x)if(des[p]!=fa[x][0]){
		dep[des[p]]=dep[x]+1;
		fa[des[p]][0]=x;
		rep(i,1,19)fa[des[p]][i]=fa[fa[des[p]][i-1]][i-1];
		dfs(des[p]);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	per(i,19,0)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	if(x==y)return x;
	per(i,19,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int dis(int x,int y){
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void bfs(){
	int h=0,t=0,maxi=0;
	q[t++]=X;mint[X]=0;vis[X]=1;
	while(h!=t){
		int x=q[h++];
		maxi=max(maxi,dep[x]-1);
		if(mark[x]){
			puts("-1");
			return;
		}
		rep2(i,0,SZ(e[x])){
			int y=e[x][i];
			if(!vis[y]&&dep[y]-1>mint[x]+1)q[t++]=y,mint[y]=mint[x]+1,vis[y]=1;
		}
	}
	printf("%d\n",maxi<<1);
}
int main(){
	read(n);read(X);read(Y);
	rep(i,1,n-1)read(a[i]),read(b[i]);
	rep(i,1,n-1){
		int x,y;read(x);read(y);
		adde(x,y);adde(y,x);
	}
	dep[Y]=1;dfs(Y);
	rep(i,1,n-1){
		if(dis(a[i],b[i])>2)mark[a[i]]=mark[b[i]]=1;
		else e[a[i]].pb(b[i]),e[b[i]].pb(a[i]);
	}
	bfs();
	return 0;
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User Vegetable
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 2124 Byte
Status AC
Exec Time 273 ms
Memory 44288 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 112 ms 32380 KB
doublestar1 AC 102 ms 31232 KB
doublestar2 AC 108 ms 31360 KB
doublestar3 AC 103 ms 31232 KB
doublestar4 AC 105 ms 31488 KB
doublestar5 AC 115 ms 32508 KB
doublestar6 AC 99 ms 31232 KB
doublestar7 AC 133 ms 32124 KB
example0 AC 7 ms 14592 KB
example1 AC 6 ms 14592 KB
example2 AC 6 ms 14592 KB
example3 AC 6 ms 14592 KB
example4 AC 6 ms 14592 KB
giri0 AC 157 ms 36736 KB
giri1 AC 143 ms 36096 KB
giri2 AC 157 ms 36224 KB
giri3 AC 160 ms 36096 KB
giri4 AC 149 ms 36096 KB
giri5 AC 161 ms 36352 KB
giri6 AC 151 ms 36352 KB
giri7 AC 144 ms 36224 KB
giri8 AC 154 ms 36224 KB
giri9 AC 172 ms 36352 KB
maxrand0 AC 144 ms 29952 KB
maxrand1 AC 148 ms 29952 KB
maxrand2 AC 156 ms 29952 KB
maxrand3 AC 108 ms 29952 KB
maxrand4 AC 108 ms 29824 KB
maxrand5 AC 114 ms 29824 KB
maxrand6 AC 110 ms 29824 KB
maxrand7 AC 134 ms 29952 KB
maxrand8 AC 133 ms 29824 KB
maxrand9 AC 113 ms 29952 KB
narashi0 AC 172 ms 35968 KB
narashi1 AC 151 ms 35968 KB
narashi2 AC 171 ms 36096 KB
narashi3 AC 186 ms 36224 KB
narashi4 AC 187 ms 36352 KB
narashi5 AC 145 ms 36224 KB
narashi6 AC 156 ms 36096 KB
narashi7 AC 180 ms 36480 KB
narashi8 AC 179 ms 36352 KB
narashi9 AC 199 ms 36096 KB
ok0 AC 234 ms 41728 KB
ok1 AC 202 ms 42624 KB
ok2 AC 194 ms 40576 KB
ok3 AC 208 ms 42752 KB
ok4 AC 202 ms 39424 KB
ok5 AC 230 ms 40448 KB
ok6 AC 264 ms 40576 KB
ok7 AC 200 ms 39168 KB
ok8 AC 249 ms 41600 KB
ok9 AC 227 ms 40960 KB
ouh0 AC 170 ms 37120 KB
ouh1 AC 207 ms 37888 KB
ouh2 AC 184 ms 38528 KB
ouh3 AC 225 ms 39040 KB
ouh4 AC 155 ms 38528 KB
ouh5 AC 183 ms 41216 KB
ouh6 AC 172 ms 41984 KB
ouh7 AC 162 ms 38016 KB
ouh8 AC 219 ms 41088 KB
ouh9 AC 210 ms 41984 KB
same0 AC 177 ms 36224 KB
same1 AC 194 ms 36096 KB
same2 AC 168 ms 36352 KB
same3 AC 147 ms 36352 KB
same4 AC 162 ms 36096 KB
same5 AC 150 ms 36096 KB
same6 AC 153 ms 36224 KB
same7 AC 173 ms 36096 KB
same8 AC 145 ms 35968 KB
same9 AC 188 ms 36352 KB
sameline0 AC 213 ms 43904 KB
sameline1 AC 219 ms 44288 KB
sameline2 AC 211 ms 41984 KB
sameline3 AC 273 ms 42880 KB
sameline4 AC 219 ms 43776 KB
sameline5 AC 209 ms 43648 KB
sameline6 AC 207 ms 40960 KB
sameline7 AC 190 ms 43392 KB
sameline8 AC 196 ms 42240 KB
sameline9 AC 211 ms 41088 KB
star0 AC 103 ms 36724 KB
star1 AC 107 ms 36596 KB
star2 AC 102 ms 36724 KB
star3 AC 107 ms 36596 KB
star4 AC 105 ms 36724 KB
star5 AC 119 ms 36724 KB
star6 AC 102 ms 36724 KB
star7 AC 108 ms 36724 KB
star8 AC 124 ms 36596 KB
star9 AC 107 ms 36852 KB
supersmall0 AC 6 ms 14592 KB
supersmall1 AC 6 ms 14592 KB
supersmall2 AC 6 ms 14592 KB
supersmall3 AC 6 ms 14592 KB
supersmall4 AC 6 ms 14592 KB
supersmall5 AC 7 ms 14592 KB
supersmall6 AC 7 ms 14592 KB
supersmall7 AC 7 ms 14592 KB
supersmall8 AC 7 ms 14592 KB
supersmall9 AC 6 ms 14592 KB