11503 - Virtual Friends

[kbr_iut]

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.

[vahid sanei]

I got Acc in 1.570 sec

[lionking]

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]

Hi every one

I solve 10608 & 10685

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

Code: Select all

CUT after ACC.............

[calicratis19]

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

[saiful_sust]

Thanks calicratis19 4 ur test case

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

[qwerty]

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

[helloneo]

Union Find algorithm is enough to get AC

[qwerty]

acc

[Shafaet_du]

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]

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]

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

[brianfry713]

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

[simon0191]

Thanks a lot ! AC

[mahade hasan]

Cutttt Acc........................