Show all threads Hide all threads Show all messages Hide all messages |
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 O(n+m) solution exists: extend <https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm> to keep not only the top of each set in the disjoint-set forest, but also the weight of the path till that top. 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 |
Any Help in Runtime error (access violation) test #13 | Maged Milad | 1471. Distance in the Tree | 30 Jul 2015 20:24 | 2 |
If anyone know hint or test case for test#13 I used RMQ and LCA to solve this Problem |
Crash (access violation) on test 1 | Abzal | 1471. Distance in the Tree | 28 Jul 2015 23:44 | 3 |
plz, help me! why i get crash(access violation). // LCA (least common ancestor) offline by using interval tree in O(logN) // Solution by Serekov Abzal #pragma comment(linker, "/STACK:16777216") #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; int ADD = 65536; int inf = 9999999; vector <vector <pair<int, int> > > graph; vector <bool> b(50001, false); vector <int> h(50001, 0); vector <int> order; vector <int> d(50001, 0); vector <int> first(50001, -1); pair <int, int> tree[2 * 65536 + 1]; int n, root = 0; void init_graph() { scanf("%d", &n); graph.resize(n); for (int i = 0; i < n - 1; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); graph[u].push_back(make_pair(v, w)); graph[v].push_back(make_pair(u, w)); } }; void dfs(int v, int p) { b[v] = true; h[v] = p; order.push_back(v); for (int i = 0; i < graph[v].size(); i++) if (!b[graph[v][i].first]) { dfs(graph[v][i].first, p + 1); order.push_back(v); } }; void bfs(int v) { queue <int> Q; Q.push(v); while (!Q.empty()) { int u = Q.front(); b[u] = true; for (int i = 0; i < graph[u].size(); i++) if (!b[graph[u][i].first]) { d[graph[u][i].first] = d[u] + graph[u][i].second; Q.push(graph[u][i].first); } Q.pop(); } }; void prepare() { h[root] = 0; dfs(root, 0); for (int i = 0; i < order.size(); i++) if (first[order[i]] == -1) first[order[i]] = i; for (int i = 0; i < n; i++) b[i] = false; d[root] = 0; bfs(root); }; int minimum(int u, int v) { int l = u, r = v, ans = inf, ver = inf; while (l <= r) { if (l % 2 == 1) { if (tree[l].second < ans) { ans = tree[l].second; ver = tree[l].first; } l++; }; if (r % 2 == 0) { if (tree[r].second < ans) { ans = tree[r].second; ver = tree[r].first; } --r; } l/=2; r/=2; } return ver; }; int lca(int u, int v) { int l = first[u] + ADD, r = first[v] + ADD; return minimum(l, r); }; void init_zaprosi() { int m; scanf("%d", &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); int ans = d[u] + d[v] - 2 * d[lca(u, v)]; printf("%d\n", ans); } }; void tree_build() { for (int i = 0; i <= 2 * ADD; i++) tree[i] = make_pair(-1, inf);
for (int i = ADD; i < ADD + order.size(); i++) { tree[i].first = order[i - ADD]; tree[i].second = h[order[i - ADD]]; } for (int i = ADD - 1; i > 0; i--) { if (tree[2 * i].first == -1 || tree[2 * i + 1].first == -1) { if (!(tree[2 * i].first == -1 && tree[2 * i + 1].first == -1)) { if (tree[2 * i].first == -1) tree[i] = tree[2 * i + 1]; else tree[i] = tree[2 * i]; } } else { if (tree[2 * i].second < tree[2 * i + 1].second) tree[i] = tree[2 * i]; else tree[i] = tree[2 * i + 1]; } } }; int main() { init_graph(); prepare(); tree_build(); init_zaprosi(); return 0; } I've just resized size of segment tree to 2 * 131072, and one thing: not everytime u < v, there can be like u > v, so i swaped them, and i got AC So, everyone assumed 0 is the root of the tree. I don't find it in the problem description. |
Is a root node for the tree? | aigoruan | 1471. Distance in the Tree | 27 Jul 2015 21:58 | 3 |
Is a root node for the tree? You mean 0 is the root of the tree? |
Problem 1471. Distance in the Tree has been rejudged | Vladimir Yakovlev (USU) | 1471. Distance in the Tree | 23 Apr 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. Distance in the Tree | 23 Feb 2015 20:33 | 1 |
WA2 Alibi 23 Feb 2015 20:33 What can it be, please? WA2 |
WA #9 | Facundo | 1471. Distance in the Tree | 14 Mar 2014 03:50 | 3 |
WA #9 Facundo 1 Feb 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 |
Why WA1? | Andrew Sboev | 1471. Distance in the Tree | 24 Jan 2014 13:26 | 4 |
I'm using Floyd-Warshall algorithm, and my program correctcly passes different tests, but i have WA1. Why? Floyd-Warshall algorithm? But it's too slow. Use LCA. Maybe it is slow, but it works correctly :)Should be TLE, not WA1 :) Use std::cout. I had such problem when I used <fstream> |