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 |
|
|
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 |