## 11503 - Virtual Friends

Moderator: Board moderators

### 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...............................

kbr_iut
Experienced poster

Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm

### Re: 11503 - Virtual Friends

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

vahid sanei
Learning poster

Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### 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 200001using 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;}`
lionking
New poster

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

### 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.
saiful_sust
Learning poster

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

### Re: 11503 - Virtual Friends

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

try these inputs
Code: Select all
`16a bb ce fe gc df g`
Heal The World
calicratis19
Learning poster

Posts: 76
Joined: Mon Jul 21, 2008 8:50 am

### Re: 11503 - Virtual Friends

Thanks calicratis19 4 ur test case

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

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

### Re: 11503 - Virtual Friends

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

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

### Re: 11503 - Virtual Friends

Union Find algorithm is enough to get AC
helloneo
Guru

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

### Re: 11503 - Virtual Friends

acc
qwerty
New poster

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

### Re: 11503 - Virtual Friends

Try this:

input:
Code: Select all
`113A FG H R T H RH HW PZ AT TE TT HL L P Q G E`

output:

Code: Select all
`2224423455135`

Use standard union find algo to solve this problem within time limit.
Shafaet_du
Experienced poster

Posts: 147
Joined: Mon Jun 07, 2010 11:43 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
SyFyKid
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 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.
simon0191
New poster

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

### Re: 11503 - Virtual Friends

Input:
Code: Select all
`120w nr lq mh bd cr ao zk wy ki hd ds qd cr xm jw or fs xy jl b`
AC output:
Code: Select all
`2222232343232446591518`
brianfry713
Guru

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

### Re: 11503 - Virtual Friends

Thanks a lot ! AC
simon0191
New poster

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

### Re: 11503 - Virtual Friends

Cutttt Acc........................
we r surrounded by happiness
need eyes to feel it!