11503 - Virtual Friends

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: 11503 - Virtual Friends....TLE ....please help....

Post by aybek » Mon Jun 30, 2014 10:30 pm

Rafiq123, explain your code. And take it into code area with tags.
Try to use sets not map ;)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11503 - Virtual Friends....TLE ....please help....

Post by brianfry713 » Mon Jul 07, 2014 11:12 pm

Don't double post.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11503 - Virtual Friends....TLE ....please help....

Post by brianfry713 » Tue Jul 08, 2014 1:47 am

Try using scanf and printf instead of cin and cout.
Check input and AC output for thousands of problems on uDebug!

vector9x
New poster
Posts: 3
Joined: Sun Jul 06, 2014 8:57 pm

Re: 11503 - Virtual Friends....TLE ....please help....

Post by vector9x » Wed Jul 09, 2014 7:39 am

You are counting for the number of elements in the set after each query... that is not efficient.
You can hold an array num_elements[N] which contains the number of elements of each set (initially 1).
When you make the union, you can do something like:

Code: Select all

...
if(u!=v)
{
    par[u]=v;
    num_elements[v] += num_elements[u];
}
then, you can get the number of elements in constant time with num_elements[find(M[name_1])]
or even better, your union function could return that value.

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re: 11503 - Virtual Friends

Post by ssavi » Fri Aug 07, 2015 9:20 pm

Hi I have solved 11503 ...
Here is my Code : http://ideone.com/34YqH9
But I need to optimize this Code .. I got AC with 2.281sec. But I want to get AC within 1 sec.
Although Time Limit : 10 sec...
How to optimize it ?

Thanks in Advance.
I know I am a Failure Guy . :(

Post Reply

Return to “Volume 115 (11500-11599)”