Submission #1680059
Source Code Expand
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<bitset> #include<map> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long LL; typedef double db; int get(){ char ch; while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-'); if (ch=='-'){ int s=0; while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0'; return -s; } int s=ch-'0'; while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0'; return s; } const int N = 2e+5+5; struct edge{ int x,nxt; }e1[N*2],e2[N*2]; int h1[N],h2[N],tot1,tot2; int n,X,Y; int dep2[N],dep1[N]; bool bz1[N],bz2[N]; int fa[N][20]; int ans; db tim; void inse(int x,int y,int *h,edge *e,int &tot){e[++tot].x=y;e[tot].nxt=h[x];h[x]=tot;} void dfs2(int x){ bz2[x]=1; fo(i,1,tim)fa[x][i]=fa[fa[x][i-1]][i-1]; for(int p=h2[x];p;p=e2[p].nxt) if (!bz2[e2[p].x]){ dep2[e2[p].x]=dep2[x]+1; fa[e2[p].x][0]=x; dfs2(e2[p].x); } } int getdis(int x,int y){ int tmp=dep2[x]+dep2[y]; if (dep2[x]<dep2[y])swap(x,y); fd(i,tim,0) if (fa[x][i]&&dep2[fa[x][i]]>=dep2[y])x=fa[x][i]; if (x==y)return tmp-2*dep2[x]; fd(i,tim,0) if (fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return tmp-2*dep2[x]+2; } void dfs1(int x){ bz1[x]=1; if (dep1[x]>=dep2[x])return; ans=max(ans,2*dep2[x]); for(int p=h1[x];p;p=e1[p].nxt) if (!bz1[e1[p].x]){ dep1[e1[p].x]=dep1[x]+1; dfs1(e1[p].x); int d=getdis(x,e1[p].x); if (d>2)ans=1e+9; } } int main(){ n=get();X=get();Y=get(); fo(i,2,n){int x=get(),y=get();inse(x,y,h1,e1,tot1);inse(y,x,h1,e1,tot1);} fo(i,2,n){int x=get(),y=get();inse(x,y,h2,e2,tot2);inse(y,x,h2,e2,tot2);} tim=log(n)/log(2); dfs2(Y); dfs1(X); printf("%d\n",ans==1e+9?-1:ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Sugigma: The Showdown |
User | samjia2000 |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 1850 Byte |
Status | AC |
Exec Time | 160 ms |
Memory | 31232 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1400 / 1400 | ||||
Status |
|
|
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 | 88 ms | 25984 KB |
doublestar1 | AC | 82 ms | 25344 KB |
doublestar2 | AC | 82 ms | 25472 KB |
doublestar3 | AC | 79 ms | 25344 KB |
doublestar4 | AC | 82 ms | 25600 KB |
doublestar5 | AC | 84 ms | 25600 KB |
doublestar6 | AC | 77 ms | 25344 KB |
doublestar7 | AC | 78 ms | 25344 KB |
example0 | AC | 3 ms | 8448 KB |
example1 | AC | 3 ms | 8448 KB |
example2 | AC | 3 ms | 8448 KB |
example3 | AC | 3 ms | 8448 KB |
example4 | AC | 3 ms | 8448 KB |
giri0 | AC | 87 ms | 25600 KB |
giri1 | AC | 90 ms | 25472 KB |
giri2 | AC | 99 ms | 25600 KB |
giri3 | AC | 90 ms | 25472 KB |
giri4 | AC | 101 ms | 25600 KB |
giri5 | AC | 96 ms | 25600 KB |
giri6 | AC | 89 ms | 25600 KB |
giri7 | AC | 92 ms | 25600 KB |
giri8 | AC | 90 ms | 25600 KB |
giri9 | AC | 95 ms | 25600 KB |
maxrand0 | AC | 77 ms | 25600 KB |
maxrand1 | AC | 108 ms | 25600 KB |
maxrand2 | AC | 91 ms | 25600 KB |
maxrand3 | AC | 75 ms | 25600 KB |
maxrand4 | AC | 83 ms | 25472 KB |
maxrand5 | AC | 100 ms | 25472 KB |
maxrand6 | AC | 74 ms | 25472 KB |
maxrand7 | AC | 81 ms | 25600 KB |
maxrand8 | AC | 70 ms | 25472 KB |
maxrand9 | AC | 78 ms | 25600 KB |
narashi0 | AC | 82 ms | 25472 KB |
narashi1 | AC | 90 ms | 25472 KB |
narashi2 | AC | 82 ms | 25472 KB |
narashi3 | AC | 89 ms | 25600 KB |
narashi4 | AC | 93 ms | 25600 KB |
narashi5 | AC | 87 ms | 25600 KB |
narashi6 | AC | 86 ms | 25600 KB |
narashi7 | AC | 90 ms | 25600 KB |
narashi8 | AC | 88 ms | 25600 KB |
narashi9 | AC | 88 ms | 25472 KB |
ok0 | AC | 119 ms | 30464 KB |
ok1 | AC | 127 ms | 31104 KB |
ok2 | AC | 105 ms | 29056 KB |
ok3 | AC | 130 ms | 31232 KB |
ok4 | AC | 121 ms | 27904 KB |
ok5 | AC | 145 ms | 28928 KB |
ok6 | AC | 127 ms | 29440 KB |
ok7 | AC | 129 ms | 27904 KB |
ok8 | AC | 114 ms | 30080 KB |
ok9 | AC | 130 ms | 29824 KB |
ouh0 | AC | 76 ms | 25856 KB |
ouh1 | AC | 86 ms | 26496 KB |
ouh2 | AC | 85 ms | 27264 KB |
ouh3 | AC | 96 ms | 27520 KB |
ouh4 | AC | 90 ms | 27008 KB |
ouh5 | AC | 115 ms | 29824 KB |
ouh6 | AC | 106 ms | 30464 KB |
ouh7 | AC | 88 ms | 26752 KB |
ouh8 | AC | 109 ms | 29312 KB |
ouh9 | AC | 134 ms | 30464 KB |
same0 | AC | 97 ms | 25600 KB |
same1 | AC | 89 ms | 25472 KB |
same2 | AC | 70 ms | 25600 KB |
same3 | AC | 72 ms | 25600 KB |
same4 | AC | 79 ms | 25472 KB |
same5 | AC | 92 ms | 25472 KB |
same6 | AC | 73 ms | 25600 KB |
same7 | AC | 89 ms | 25600 KB |
same8 | AC | 70 ms | 25472 KB |
same9 | AC | 98 ms | 25600 KB |
sameline0 | AC | 124 ms | 30848 KB |
sameline1 | AC | 160 ms | 30976 KB |
sameline2 | AC | 104 ms | 29568 KB |
sameline3 | AC | 125 ms | 30208 KB |
sameline4 | AC | 98 ms | 30720 KB |
sameline5 | AC | 146 ms | 30720 KB |
sameline6 | AC | 107 ms | 28928 KB |
sameline7 | AC | 152 ms | 30464 KB |
sameline8 | AC | 111 ms | 29696 KB |
sameline9 | AC | 137 ms | 28928 KB |
star0 | AC | 72 ms | 25472 KB |
star1 | AC | 72 ms | 25472 KB |
star2 | AC | 58 ms | 25472 KB |
star3 | AC | 75 ms | 25472 KB |
star4 | AC | 77 ms | 25600 KB |
star5 | AC | 77 ms | 25600 KB |
star6 | AC | 60 ms | 25600 KB |
star7 | AC | 78 ms | 25472 KB |
star8 | AC | 72 ms | 25472 KB |
star9 | AC | 73 ms | 25600 KB |
supersmall0 | AC | 3 ms | 8448 KB |
supersmall1 | AC | 3 ms | 8448 KB |
supersmall2 | AC | 3 ms | 8448 KB |
supersmall3 | AC | 3 ms | 8448 KB |
supersmall4 | AC | 3 ms | 8448 KB |
supersmall5 | AC | 3 ms | 8448 KB |
supersmall6 | AC | 3 ms | 8448 KB |
supersmall7 | AC | 3 ms | 8448 KB |
supersmall8 | AC | 3 ms | 8448 KB |
supersmall9 | AC | 3 ms | 8448 KB |