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

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11503 - Virtual Friends

Post by kbr_iut » Tue Mar 03, 2009 9:59 pm

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.
thanx in advance.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

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

Re: 11503 - Virtual Friends

Post by vahid sanei » Thu Mar 05, 2009 8:50 am

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

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

Re: 11503 - Virtual Friends

Post by lionking » Tue Aug 25, 2009 5:06 pm

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

Post by saiful_sust » Tue Sep 08, 2009 6:50 pm

Hi every one

I solve 10608 & 10685

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

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
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11503 - Virtual Friends

Post by calicratis19 » Wed Sep 09, 2009 6:17 pm

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

Post by saiful_sust » Sat Sep 12, 2009 9:06 am

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

Post by qwerty » Thu Feb 25, 2010 2:47 pm

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

Post by helloneo » Thu Feb 25, 2010 3:16 pm

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

Post by qwerty » Thu Feb 25, 2010 5:12 pm

acc

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11503 - Virtual Friends

Post by Shafaet_du » Mon Mar 14, 2011 9:25 pm

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

Post by SyFyKid » Wed May 30, 2012 5:38 pm

vahid sanei wrote:I got Acc in 1.570 sec :D
heh... c++ and 1.570 ?
I've got AC with java in a quite nice time... but it sure can be more optimized. :D
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

Post by simon0191 » Sun Aug 05, 2012 1:34 am

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

Post by brianfry713 » Tue Aug 07, 2012 1:14 am

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

Post by simon0191 » Tue Aug 07, 2012 3:36 am

Thanks a lot ! AC :)

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11503 - Virtual Friends

Post by mahade hasan » Sat Oct 06, 2012 6:46 am

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

Post Reply

Return to “Volume 115 (11500-11599)”