Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Страница 3 |
WA 12 | hotguy6pack | 1471. Расстояние в дереве | 8 апр 2022 06:51 | 1 |
WA 12 hotguy6pack 8 апр 2022 06:51 |
WA on test 10 | yuety25 | 1471. Расстояние в дереве | 29 дек 2021 00:51 | 1 |
Can anybody tell me test 10? |
hint solution | mastercopycode | 1471. Расстояние в дереве | 4 авг 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. Расстояние в дереве | 4 авг 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. Расстояние в дереве | 20 апр 2021 23:09 | 2 |
WA 5 Solus 18 апр 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 |
TESTS | Solus | 1471. Расстояние в дереве | 17 апр 2021 19:40 | 1 |
TESTS Solus 17 апр 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. Расстояние в дереве | 16 авг 2020 20:33 | 1 |
Max distance may be equal 5e4 * 1e3 = 5e7. I use INF = 1e6 and spent all day to find this bug. |
Страница 2 |
Runtime Error 14 | Михаил | 1471. Расстояние в дереве | 15 апр 2020 23:51 | 1 |
|
#Test_13 | Nobodyquennteam | 1471. Расстояние в дереве | 4 апр 2020 14:52 | 1 |
#Test_13 Nobodyquennteam 4 апр 2020 14:52 |
WA in teste case 12 | Auro Soares | 1471. Расстояние в дереве | 5 авг 2019 07:32 | 1 |
Anyone can give me this test case? |
AC in 0.249 and 8668 KB (RMQ for lca) | sak3t | 1471. Расстояние в дереве | 15 июн 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. |
Java | Dmitri Belous | 1471. Расстояние в дереве | 10 мар 2017 00:06 | 1 |
Java Dmitri Belous 10 мар 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 |
WA on test 5 | Abhishek | 1471. Расстояние в дереве | 8 дек 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 |
Any Help in Runtime error (access violation) test #13 | Maged Milad | 1471. Расстояние в дереве | 30 июл 2015 20:24 | 2 |
If anyone know hint or test case for test#13 I used RMQ and LCA to solve this Problem |
Problem 1471. Distance in the Tree has been rejudged | Vladimir Yakovlev (USU) | 1471. Расстояние в дереве | 23 апр 2015 11:43 | 2 |
- New tests added - Time limit is set to 1 sec (was 2 sec) 78 authors have lost AC after rejudge. Nice rejudge, I've got ML 1 with 200 KB memory usage |
WA2 | Alibi | 1471. Расстояние в дереве | 17 апр 2021 20:38 | 2 |
WA2 Alibi 23 фев 2015 20:33 What can it be, please? WA2 |
hint | ASK | 1471. Расстояние в дереве | 28 сен 2018 14:31 | 2 |
hint ASK 8 фев 2014 21:38 Re: hint Irakli Khomeriki 28 сен 2018 14:31 is it doing search in O(1) for each pair of nodes? |
wrong answer on test 1 | kirill | 1471. Расстояние в дереве | 24 янв 2014 13:18 | 1 |
My program works true on test from conditions and on two my tests. Tell me please, what's a problem? |
if there is no path from u to v , what's the output? | invokerj | 1471. Расстояние в дереве | 29 май 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 |
WA #9 | Facundo | 1471. Расстояние в дереве | 14 мар 2014 03:50 | 3 |
WA #9 Facundo 1 фев 2013 06:48 Anyone knows what's test 9 ? I'm getting WA but my algo work in all cases I test. what was the problem i am getting wa #9 aswell |