## 11503 - Virtual Friends

Moderator: Board moderators

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 11503 - Virtual Friends

vahid sanei wrote:I got Acc in 2.920 sec , how can i reduce time of my algo ?
I use union-find and map
Mine took 6.49 sec.I also used union-find algo and map......I am asking u how urs took such a shorter time.
I saw somene getting AC in more shorter time in statistics.

If u need to check my code, tell me. I will pm you. I wonder how my code took such a long time.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11503 - Virtual Friends

I got Acc in 1.570 sec
Impossible says I`m possible

lionking
New poster
Posts: 9
Joined: Tue Feb 17, 2009 6:46 pm

### Re: 11503 - Virtual Friends

Could someone gives me some I/O?

I got WA...

here is my code, thx

Code: Select all

``````#include <iostream>
#include <string>
#include <map>
#define MAX_PEOPLE 200001

using namespace std ;

int *group = new int[MAX_PEOPLE],
*table = new int[MAX_PEOPLE];

int check(int x)
{
int root = table[x];
if(root != x)
return (table[x] = check(root));
else
return x;
}

int UNION(int x, int y)
{
int rootA = check(x), rootB = check(y);
if(table[rootA] != table[rootB]){
if(group[rootA] < group[rootB]){
table[rootA] = rootB;
group[rootA] = (group[rootB] += group[rootA]);
}
else{
table[rootB] = rootA;
group[rootB] = (group[rootA] += group[rootB]);
}
}
return group[rootA];
}

int main()
{
int T, F, i, posA, posB, people;
string name1, name2;
map<string, int> hashmap;

cin.sync_with_stdio(false); cout.sync_with_stdio(false);
cin >> T;
while(T){
memset(table, 0, MAX_PEOPLE); memset(group, 0, MAX_PEOPLE);

cin >> F;
people = 0;
for(i=0; i<F; ++i){
cin >> name1 >> name2;
if(hashmap.find(name1) == hashmap.end()){
hashmap[name1] = people;
table[people] = people;
group[people] = 1;
posA = people;
++people;
}
else
posA = hashmap[name1];
if(hashmap.find(name2) == hashmap.end()){
hashmap[name2] = people;
table[people] = people;
group[people] = 1;
posB = people;
++people;
}
else
posB = hashmap[name2];
cout << UNION(posA, posB);
putchar('\n');
}
--T;
}

delete [] group; delete [] table;
return 0;
}``````

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11503 - Virtual Friends

Hi every one

I solve 10608 & 10685

But got WA in this problem.........
Some one PLZ help me

Code: Select all

``````CUT after ACC.............
``````
Last edited by saiful_sust on Sat Sep 12, 2009 9:03 am, edited 1 time in total.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### Re: 11503 - Virtual Friends

you are not properly handeling the cases where two nodes cant be connected.

try these inputs

Code: Select all

``````1
6
a b
b c
e f
e g
c d
f g
``````
Heal The World

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11503 - Virtual Friends

Thanks calicratis19 4 ur test case

Just a silly mistake I edit my code and got acc ....

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re: 11503 - Virtual Friends

i am getting TLE for n=100000 i think.Even my computer takes time for that.any efficiency hint please?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11503 - Virtual Friends

Union Find algorithm is enough to get AC

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re: 11503 - Virtual Friends

acc

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11503 - Virtual Friends

Try this:

input:

Code: Select all

``````1
13
A F
G H
R T
H R
H H
W P
Z A
T T
E T
T H
L L
P Q
G E
``````
output:

Code: Select all

``````2
2
2
4
4
2
3
4
5
5
1
3
5

``````
Use standard union find algo to solve this problem within time limit.

SyFyKid
New poster
Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 11503 - Virtual Friends

vahid sanei wrote:I got Acc in 1.570 sec
heh... c++ and 1.570 ?
I've got AC with java in a quite nice time... but it sure can be more optimized.
11503 - Virtual Friends Accepted Java 1.124 0.104 161

simon0191
New poster
Posts: 2
Joined: Sun Aug 05, 2012 1:21 am

### Re: 11503 - Virtual Friends

Hi, I'm getting WA but I really don't know why ... I've tried all the test cases in this thread and for all I get the correct output but I still get WA.
Here's my code ...

Code: Select all

``````AC
``````
Last edited by simon0191 on Tue Aug 07, 2012 3:38 am, edited 1 time in total.

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

### Re: 11503 - Virtual Friends

Input:

Code: Select all

``````1
20
w n
r l
q m
h b
d c
r a
o z
k w
y k
i h
d d
s q
d c
r x
m j
w o
r f
s x
y j
l b``````
AC output:

Code: Select all

``````2
2
2
2
2
3
2
3
4
3
2
3
2
4
4
6
5
9
15
18``````
Check input and AC output for thousands of problems on uDebug!

simon0191
New poster
Posts: 2
Joined: Sun Aug 05, 2012 1:21 am

### Re: 11503 - Virtual Friends

Thanks a lot ! AC