Show all threads Hide all threads Show all messages Hide all messages |
hint | 👾_challenger128_[PermSU] | 1056. Centers of the Net | 13 Mar 2021 00:05 | 1 |
hint 👾_challenger128_[PermSU] 13 Mar 2021 00:05 th: deleting leafes doesn't change centers |
Idea O(N) | Felix_Mate | 1056. Centers of the Net | 4 Nov 2019 15:11 | 2 |
I got AC! It's nice problem! My algo works at O(3*N)=O(N). 1)BFS from any vertex and find the most remote vertex (let V); 2)BFS from V and find the most remote vertex (let U); 3)Create path from U and V; vertex(vertexes) in the middle is answer. Edited by author 04.08.2015 12:56 |
hint | arun | 1056. Centers of the Net | 6 Jun 2016 10:53 | 1 |
hint arun 6 Jun 2016 10:53 try to locate the centre of the diameter of the tree ! O(N) |
How to make it faster than O(n^2) | [NU GYM] I am get tester... | 1056. Centers of the Net | 23 Apr 2015 03:36 | 5 |
Wow! O(n^2) is worked. I got Ac by time 1.3. But how solve it faster? One possible solution is to find the most distant computer(let's call it x) from the first, and then start BFS from it. The path from the last added in the BFS and x is the longest tree chain. So the middle nodes are the wanted answer. (if the chain has odd number of nodes, the answer will be n/2, and if it's even they will be n/2 and n/2+1) Well, Blade, it seems it's a well known solution here in Bulgaria :) My soulotion is O(n^2) but TLE on test 9.Here is my soulution. #include <iostream> #include <algorithm> using namespace std; int n; int way[10001][2]; int ps_max(int start) //Obxod(poisk) v shirinu { int *label,i,p(0),k(1),*fifo,cur; label=new int [n]; fifo=new int [n]; for(i=0;i<n;i++) { label[i]=32767; } label[start]=0; int max=0; fifo[p]=start; while(p!=k) { cur=fifo[p]; p++; for(i=0;i<n-1;i++) { if ((way[i][0]==cur || way[i][1]==cur)) { if (way[i][0]==cur && label[way[i][1]]>label[cur]+1) { label[way[i][1]]=label[cur]+1; if (label[way[i][1]]>=max) { max=label[way[i][1]]; } fifo[k]=way[i][1]; k++; } else if (way[i][1]==cur && label[way[i][0]]>label[cur]+1) { label[way[i][0]]=label[cur]+1; if (label[way[i][0]]>=max) { max=label[way[i][0]]; } fifo[k]=way[i][0]; k++; } } } } return max; } int main() { int i,t,min(100000); cin>>n; int *center; center=new int [n]; for(i=1;i<n;i++) { cin>>t; t--; way[i-1][0]=t; way[i-1][1]=i; } for(i=0;i<n;i++) { center[i]=ps_max(i); if (center[i]<=min) { min=center[i]; } } for(i=0;i<n;i++) { if (center[i]==min) cout<<i+1<<" "; } return 0; } There is an easy O(n) solution. Lets call vertexes that has only one neighbour(another vertex connected by edge) "lonely". Remove all lonely vertexes. Afterwards remove all lonely vertexes. Afterwards remove all lonely vertexes. Basically what we are doing is trimming the longest route from both sides. In the end there will be left only 1 or two vertexes(if longest path contains even amount of vertexes). Last vertexes will be the middle ones. |
WA2 help PLEASE! | Kate | 1056. Centers of the Net | 22 Dec 2013 20:48 | 1 |
|
переведите задание | efg | 1056. Centers of the Net | 1 Oct 2012 15:37 | 1 |
|
diametr | Abzal | 1056. Centers of the Net | 27 Jun 2012 01:47 | 2 |
this problem is solved by using diametr of graph, isn't it?! Re: diametr Alexey Dergunov [Samara SAU] 27 Jun 2012 01:47 |
hint on solution | askhatik | 1056. Centers of the Net | 22 Jun 2012 18:46 | 1 |
use DFS with memorization |
please can anybody provide me some test cases i am getting WA on test 4 | Anupam Ghosh,Bengal Engg and Science University,Shibpur,India | 1056. Centers of the Net | 22 Aug 2011 16:29 | 2 |
please can anybody provide me some test cases i am getting WA on test 4. secondly what is meant by remote computers?? remote - means the further |
Why I get TLE when I use forwards star but AC for vector? | Power_OJ4 | 1056. Centers of the Net | 2 Aug 2011 07:18 | 1 |
// forwards star int num,adj[10005]; struct edge {int v,pre;}e[10005]; void insert(int u,int v) { e[num].v=v; e[num].pre=adj[u]; adj[u]=num++; } for(i=adj[x];~i;i=e[i].pre) { } Edited by author 02.08.2011 07:19 |
:-))) | Qafqaz Sehriyar Novruzov | 1056. Centers of the Net | 17 Jun 2011 15:51 | 1 |
:-))) Qafqaz Sehriyar Novruzov 17 Jun 2011 15:51 |
what algo should i use,I had memory limit,then time limit and now again time limi 2.046s 1.037kb? | Hrayr | 1056. Centers of the Net | 17 Jun 2011 14:34 | 2 |
what algo should i use,I had memory limit,then time limit and now again time limit 2.046s 1.037kb? |
I know 2 souluions,first gets TLE test9 and second gets MLE test 9.How can i use less memory or a little time. | Hrayr | 1056. Centers of the Net | 12 Jun 2011 20:18 | 1 |
I know 2 souluions,first gets TLE test9 and second gets MLE test 9.How can i use less memory or a little time. Edited by author 12.06.2011 20:18 Edited by author 12.06.2011 20:18 |
How to get memory less than 16 mb? | Hrayr | 1056. Centers of the Net | 3 Jun 2011 23:12 | 1 |
I used graf[n][n] and got MLE on test9.My solution is O(n^2). Edited by author 05.06.2011 15:08 |
why I was WA5,who can tell me what the test 5 like? | uuu | 1056. Centers of the Net | 21 Apr 2010 20:32 | 1 |
|
Hint O(n^2) | Hanzbrow (TNU) KCC | 1056. Centers of the Net | 16 Apr 2010 21:14 | 2 |
vector<set<int> > and if WA 5 then test this: 9 1 2 3 4 5 6 7 8 and 10 1 2 3 4 5 6 7 8 9 Hmmmmm.... O(n^2) is too slow (-_-). I know O(N+M) solution.You have just to delte leaves, while number of vertex>2.If you will do it righ,you will get O(N+M)solution. |
Can somebody give me some hints on how to solve P1056? | abc | 1056. Centers of the Net | 12 Feb 2010 20:09 | 7 |
1. the graph forms a tree 2. you need to give this tree direction (since the given tree is undirected) 3. the longest path starting at node k is the maximum of 2 values: the maximum path starting at k and going DOWN (a tree has no cycles so you can solve this easily in linear time, i used simple DP) and the maximum path by going UP from k. "the maximum path by going UP from k." What do you mean by this? How to calculate the maximum path by going up from k Just invert directions of all edges and calculate the maximum path by going DOWN form k. Realization of this thing is much easier than its description. Just cut off leafs of tree step by step while count of nodes >2! Edited by author 25.06.2005 14:44 Far not the fastest solution, but passed (0.375 sec): 1. make a bidirectional graph, connectivity of which will be kept in an array of vectors 2. start dfs from each of the verticies which are not leaves and calculate the longest path 3. Note that if there are 2 vertices, the answer is always "1 2" The solution might run in O(N*(N+M)) time, as I guess Edited by author 15.02.2010 13:13 Edited by author 15.02.2010 13:13 |
I have the O(n) algorithm,do you want to know? | Huang Yizheng | 1056. Centers of the Net | 12 Aug 2009 07:34 | 4 |
YES, you are like salesman now. I think we can find answer_depth of roots for O(N) - let's consider d - diameter of tree, if d mod 2 = 0 then ans_depth = d div 2 else ans_depth = d div 2 + 1 Edited by author 30.08.2008 15:39 Edited by author 30.08.2008 15:40 |
Maybe test data is weak?(-) | tiancaihb | 1056. Centers of the Net | 6 Aug 2009 14:58 | 2 |
For data:5 5 4 5 1 I know it's illegal according to the statement,but it's the only one I can find now. However,I believe there is an "legal" one which may make some AC prog wrong ans! My AC prog says 5 4! I used bfs twice,and I didn't sort the 2 numbers! Perhaps there is no data figures out this problem. btw,I fixed my prog at once.Sorry for my poor English. Edited by author 06.08.2009 14:41 Edited by author 06.08.2009 14:47 Sorry,but now I know maybe there isn't a "legal" data that makes error. I can't prove it well,but it's true:when use 2bfs,you needn't sort 2 num. See: Divide the tree into 2 parts,L and R. The answer,if 2 num,must be in the longer part.Let's say it's on the right. First you bfs to right,then bfs to leftmost. When you follow the longest chain back again,you are going to right side. If the data is legal,part R is in inscend(I don't know how to spell) order.So ans num1<ans num2. so you needn't sort them at all! |
why WA Orz......PLZ help me` | OPheadache_h | 1056. Centers of the Net | 5 Aug 2009 20:56 | 1 |
var n,i,j,k,x:longint; f:array[1..10000,0..100]of longint; ff:array[1..10000]of boolean; begin readln(n); fillchar(f,sizeof(f),0); for i:=2 to n do begin readln(x); inc(f[i,0]); inc(f[x,0]); f[i,f[i,0]]:=x; f[x,f[x,0]]:=i; end; fillchar(ff,sizeof(ff),true); while n>2 do begin for i:=1 to n do if f[i,0]=1 then begin dec(f[i,0]); ff[i]:=false; dec(f[f[i,1],0]); for j:=1 to f[f[i,1],0] do if f[f[i,1],j]=i then begin for k:=j to f[f[i,1],0] do f[f[i,1],k]:=f[f[i,1],k+1]; break; end; dec(n); end; end; if n=1 then for i:=1 to n do if ff[i] then writeln(i); if n=2 then begin for i:=1 to n do if ff[i] then begin write(i,' '); break; end; for i:=i+1 to n do if ff[i] then writeln(i); end; end. |