793 - Network Connections

[apcastelein]

Ok thanks. I've adjusted my code. Now I get runtime error

Code: Select all

I got AC Thanks :)

[brianfry713]

Print a blank line between test cases.

[lighted]

Each case (except last) ends with blank line. Change reading to

Code: Select all

scanf("%d",&n);

while (getchar() != '\n') ;

UFDS* set=new UFDS(n);

char line[100];

while(gets(line)  &&  sscanf(line, " %c %d %d", &type, &i, &j) == 3) {

Don't forget to remove your code after getting accepted.

[Degiac]

I keep getting WA, even though I ran every test from this thread successfully on my PC. Am I missing something in my code?

Code: Select all

#include <cstdio>

using namespace std;

int pc[1000];
int rank[1000];

int parent(int i) { return (pc[i] == i) ? i : (pc[i] = parent(pc[i])); }

bool isConnected(int i, int j) { return parent(i) == parent(j); }

void join(int i, int j)
{
    if(!isConnected(i, j))
    {
		int x = parent(i), y = parent(j);
		if(rank[x] > rank[y]) pc[y] = x;
		else { pc[x] = y; if(rank[x] == rank[y]) rank[y]++; }
    }   
}

int main()
{
    int T; scanf("%d\n", &T);
    while(T--)
    {
		int N;
		scanf("\n%d\n", &N);
		for(int i = 0; i < N; i++) { pc[i] = i; rank[i] = 0; }
		char c;
		int i, j;
		int succ = 0, fail = 0;
		while(scanf("%c %d %d\n", &c, &i, &j) == 3)
		{
			i--; j--;
			if(c == 'c') join(i, j);
			else isConnected(i, j) ? succ++ : fail++;
		}

		printf("%d,%d\n", succ, fail); if(T != 0) printf("\n");
	}
        return 0;
}

[brianfry713]

Change your input parsing to read line by line.

[apcastelein]

I printed a blank line between test cases as brianfry713 said but that wasn't enough to get AC. After implenting lighted's modification it worked but I don't understand how that change works since I seem to be getting the same output for all of my test cases.

[brianfry713]

I can't answer your question without seeing your old code.

[apcastelein]

Sorry my bad

Old Code:

Code: Select all

Thank you

[lighted]

Input

Code: Select all

2

4
c 1 4
c 2 4
q 1 3
q 1 4

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5

Acc. Output

Code: Select all

1,1

1,2

[brianfry713]

Input:

Code: Select all

1

2
q 1 2
q 1 2

AC output:

Code: Select all

0,2

[alecassis]

I'm passing every test case but keep getting WA.

Can anybody help me?
thanks in advance

Code: Select all

code removed after AC
pd: don't forget that computers go from 1 to N, that was my problem

[jporcelli1120]

Can somebody tell me whats the deal with this problem? The currently described problems input format doesn't say anything about multiple test cases yet I get WA, so I feel like it really is for multiple test cases. But then Even when I add handling for multiple test cases I still get WA. Is my input format messing something up, I have seen a lot of posts about weird input, or am i wrong? Thanks guys.

Update: I removed a piece of logic I threw in when I first got WA to see if the problem was that queries of the form x x should be connected or disconnected. I was just checking since I didn't know why WA, but it turns out it was because I wasn't handling multiple test cases when THERE IS INDEED MULTIPLE TEST CASES even though the description is not worded that way. I guess this belongs in the mistakes section I will notify the UVa guys

[alekscooper]

Hello guys,

I'm just going to start doing this problem after reading a piece on Union Find in Algorithms by R. Sedgewick.

Unlike you all, I would like to do it in Java.

Knowing that input/output might be a pain, I'd like to ask you what the multiple input problem is. I found here and there that it is NOT mentioned in the sample input given by UVa problem description. However, when I see that it contains 2 cases: 10 computers (for which 1,2 is the sample output) and 1 computer (2,0).

What is this problem?

Thanks for your help.