ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1056. Centers of the Net

How to make it faster than O(n^2)
Posted by [NU GYM] I am get tester... 16 Nov 2005 17:44
Wow!
O(n^2) is worked.
I got Ac by time 1.3.
But how solve it faster?
Re: How to make it faster than O(n^2)
Posted by IYI_Blade 30 Apr 2006 03:15
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)
Re: How to make it faster than O(n^2)
Posted by Todor Tsonkov 10 Aug 2006 12:20
Well, Blade, it seems it's a well known solution here in Bulgaria :)
Re: How to make it faster than O(n^2)
Posted by Hrayr 12 Jun 2011 22:09
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;
}
Re: How to make it faster than O(n^2)
Posted by lakerka 23 Apr 2015 03:36
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.