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