th: deleting leafes doesn't change centers 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 try to locate the centre of the diameter of the tree ! O(N) 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. this problem is solved by using diametr of graph, isn't it?! use DFS with memorization 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 // 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 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. Edited by author 12.06.2011 20:18 Edited by author 12.06.2011 20:18 I used graf[n][n] and got MLE on test9.My solution is O(n^2). Edited by author 05.06.2011 15:08 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. 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 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 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! 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. |
|