Show all threads Hide all threads Show all messages Hide all messages |
WA 12 | hotguy6pack | 1471. Distance in the Tree | 8 Apr 2022 06:51 | 1 |
WA 12 hotguy6pack 8 Apr 2022 06:51 |
WA on test 10 | yuety25 | 1471. Distance in the Tree | 29 Dec 2021 00:51 | 1 |
Can anybody tell me test 10? |
hint solution | mastercopycode | 1471. Distance in the Tree | 4 Aug 2021 01:29 | 1 |
you can use Binary Lifting,find lca of u and v you find distance u with root of tree the result=dis[a]+dis[b]-2*dis[lca(a,b)] |
WA on test 8 | Nazmus Sakib | 1471. Distance in the Tree | 4 Aug 2021 01:26 | 2 |
No clue as to what's wrong. Can anyone please give me a hint or what's the case? you can show your code , i can help you |
WA 5 | Solus | 1471. Distance in the Tree | 20 Apr 2021 23:09 | 2 |
WA 5 Solus 18 Apr 2021 20:51 What can it be?(tests or ideas, something pls) passes 3 0 1 1 1 2 0 1 1 2 ans: 0 but still WA Edited by author 20.04.2021 00:52 try 5 0 1 1 1 2 1 3 0 1 0 4 1 4 0 4 4 0 0 2 2 0 |
WA2 | Alibi | 1471. Distance in the Tree | 17 Apr 2021 20:38 | 2 |
WA2 Alibi 23 Feb 2015 20:33 What can it be, please? WA2 |
TESTS | Solus | 1471. Distance in the Tree | 17 Apr 2021 19:40 | 1 |
TESTS Solus 17 Apr 2021 19:40 5 0 1 1 0 2 1 1 3 1 1 4 1 2 3 2 4 3 ans: 3 2 5 1 0 1 2 0 1 3 1 1 4 1 1 2 2 3 4 3 ans: 3 2 3 2 1 1 0 2 1 3 0 0 0 1 1 1 ans: 0 2 0 5 0 1 1 0 2 2 1 3 3 1 4 1 2 2 3 4 3 6 4 ans: 6 4 8 0 1 1 0 2 1 2 3 1 3 4 1 0 5 1 5 6 1 6 7 1 6 7 7 1 4 4 4 4 3 3 4 7 0 ans: 0 4 0 1 1 3 5 0 1 1 1 2 1 3 0 1 0 4 1 4 0 4 4 0 0 2 2 0 ans: 1 1 2 2 Edited by author 17.04.2021 20:29 Edited by author 17.04.2021 20:50 Edited by author 20.04.2021 00:30 Edited by author 20.04.2021 00:41 Edited by author 20.04.2021 23:06 |
WA13: Hint | KostyaRychkov | 1471. Distance in the Tree | 16 Aug 2020 20:33 | 1 |
Max distance may be equal 5e4 * 1e3 = 5e7. I use INF = 1e6 and spent all day to find this bug. |
Runtime Error 14 | Михаил | 1471. Distance in the Tree | 15 Apr 2020 23:51 | 1 |
|
#Test_13 | Nobodyquennteam | 1471. Distance in the Tree | 4 Apr 2020 14:52 | 1 |
#Test_13 Nobodyquennteam 4 Apr 2020 14:52 |
WA in teste case 12 | Auro Soares | 1471. Distance in the Tree | 5 Aug 2019 07:32 | 1 |
Anyone can give me this test case? |
WA on test 5 | Abhishek | 1471. Distance in the Tree | 8 Dec 2018 12:26 | 2 |
Can anybody tell me test 5,i am getting WA.I have tried my code on many random cases and it works fine. Code:- #include<bits/stdc++.h> #define PB push_back #define MP make_pair #define F first #define S second #define SZ(a) (int)(a.size()) #define SET(a,b) memset(a,b,sizeof(a)) #define LET(x,a) __typeof(a) x(a) #define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++) #define loop(i,a,b) for(int i=a;i<b;i++) #define si(n) scanf("%d",&n) #define sll(n) scanf("%lld",&n) #define sortv(a) sort(a.begin(),a.end()) #define all(a) a.begin(),a.end() #define bitcount(n) __builtin_popcount(n) #define DRT() int t; cin>>t; while(t--) #define TRACE #ifdef TRACE #define trace1(x) cerr << #x << ": " << x << endl; #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl; #define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl; #define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl; #define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl; #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl; #else #define trace1(x) #define trace2(x, y) #define trace3(x, y, z) #define trace4(a, b, c, d) #define trace5(a, b, c, d, e) #define trace6(a, b, c, d, e, f) #endif using namespace std; typedef long long int lli; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector< vi > vvi; typedef vector< ii > vii; lli modpow(lli a,lli n,lli temp){lli res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;} //***********************************END OF TEMPLATE********************************************************************* const int MAX = 50005,MAX2=log2(MAX); int d[MAX],h[MAX],P[MAX][MAX2],n; vector<vii> graph(MAX); void dfs(int u,int p){ P[u][0]=p; h[u]=h[p]+1; for(auto k:graph[u]){ if(k.F==p)d[u]=d[p]+k.S; else dfs(k.F,u); } } void init(){ for(int i=0;i<n;++i){ for(int j=0;(1<<j)<n;++j)P[i][j]=-1; } d[0]=0; h[0]=-1; dfs(0,0); for(int j=1;(1<<j)<n;++j){ for(int i=0;i<n;++i){ if(P[i][j-1]!=-1)P[i][j]=P[P[i][j-1]][j-1]; } } } int lca(int u,int v){ if(h[u]>h[v])swap(u,v); int l=log2(h[v]); for(int i=l;i>=0;--i){ if(h[v]-(1<<i)>=h[u]&&P[v][i]!=-1)v=P[v][i]; } //u and v at same level if(u==v)return u; for(int i=l;i>=0;--i){ if(P[u][i]!=P[v][i]&&P[u][i]!=-1){ u=P[u][i]; v=P[v][i]; } } return P[u][0]; } int query(int u,int v){ int lc = lca(u,v); return d[u]+d[v]-2*d[lc]; } int main(){ int u,v,w,q; si(n); loop(i,1,n){ si(u);si(v);si(w); graph[u].PB(MP(v,w)); graph[v].PB(MP(u,w)); } init(); si(q); while(q--){ si(u);si(v); printf("%d\n",query(u,v)); } return 0; } Edited by author 17.01.2016 01:13 |
WA#4 | vessel | 1471. Distance in the Tree | 8 Dec 2018 11:57 | 2 |
WA#4 vessel 6 Dec 2006 18:05 wa#4 for countless times, seek for kind help! thanks Re: WA#4 MOPDOBOPOT (USU) 8 Dec 2018 11:57 |
hint | ASK | 1471. Distance in the Tree | 28 Sep 2018 14:31 | 2 |
hint ASK 8 Feb 2014 21:38 Re: hint Irakli Khomeriki 28 Sep 2018 14:31 is it doing search in O(1) for each pair of nodes? |
Which is the father node? | Roby | 1471. Distance in the Tree | 6 Jan 2018 11:31 | 4 |
u and v,which is the father node? There's no father node. You can do topsort and choose it yourself. Um... You can't topsort a given tree, because it's an undirected graph. |
Anyone crash test#2 | abc | 1471. Distance in the Tree | 14 Nov 2017 20:25 | 2 |
Test #2 contains graph with only one node |
AC in 0.249 and 8668 KB (RMQ for lca) | sak3t | 1471. Distance in the Tree | 15 Jun 2017 22:06 | 2 |
used RMQ using segment tree to find lca in log(n) total time complexity O(n+q*(lgn)) = O(q*lgn) Almost the same numbers (0.268, 11500) for table for 2^i -th ancestor. |
if there is no path from u to v , what's the output? | invokerj | 1471. Distance in the Tree | 29 May 2017 15:33 | 2 |
solved. thanks Edited by author 26.12.2013 09:01 There will always be one and only one path between any two vertices. josh me aake likh diya :D Edited by author 29.05.2017 15:34 |
Java | Dmitri Belous | 1471. Distance in the Tree | 10 Mar 2017 00:06 | 1 |
Java Dmitri Belous 10 Mar 2017 00:06 On Java I reccomend to use ArrayList instead Stack. It saved me about 0.4 sec. Edited by author 10.03.2017 00:06 |
test #5 | andrei parvu | 1471. Distance in the Tree | 22 Jan 2017 22:44 | 5 |
test #5 andrei parvu 17 Aug 2008 00:54 can anyone tell me what is the 'problem' with test #5, because I get stack overflow, although I don't declare any local variables in my recursive function (I use a vector to simulate the stack) I have the same problem ,first! but I find that test#5 may be not a tree! for example: 3 0 1 1 1 0 1 1 0 1 so you should use array to record whether a node have been in the stack. sorry: the example is 4 0 1 1 1 2 1 2 0 1 1 0 1 But your example is not a tree... there are cicle... Re: test #5 Mescheryakov_Kirill [SESC17]💻 by Kirom 22 Jan 2017 22:44 |