793 - Network Connections

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 793 - Network Connections

Post by apcastelein » Mon Sep 01, 2014 7:53 pm

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

Code: Select all

I got AC Thanks :)
Last edited by apcastelein on Mon Sep 08, 2014 11:01 pm, edited 1 time in total.

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

Re: 793 - Network Connections

Post by brianfry713 » Wed Sep 03, 2014 7:44 pm

Print a blank line between test cases.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 793 - Network Connections

Post by lighted » Wed Sep 03, 2014 8:14 pm

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. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Degiac
New poster
Posts: 2
Joined: Thu Sep 04, 2014 11:41 pm
Location: Salerno, Italy
Contact:

Re: 793 - Network Connections

Post by Degiac » Thu Sep 04, 2014 11:51 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 793 - Network Connections

Post by brianfry713 » Sat Sep 06, 2014 7:31 am

Change your input parsing to read line by line.
Check input and AC output for thousands of problems on uDebug!

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 793 - Network Connections

Post by apcastelein » Mon Sep 08, 2014 11:04 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 793 - Network Connections

Post by brianfry713 » Tue Sep 09, 2014 7:02 pm

I can't answer your question without seeing your old code.
Check input and AC output for thousands of problems on uDebug!

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 793 - Network Connections

Post by apcastelein » Tue Sep 09, 2014 7:07 pm

Sorry my bad

Old Code:

Code: Select all

Thank you
Last edited by apcastelein on Tue Sep 16, 2014 11:51 pm, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 793 - Network Connections

Post by lighted » Wed Sep 10, 2014 1:39 pm

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

Re: 793 - Network Connections

Post by brianfry713 » Tue Sep 30, 2014 12:11 am

Input:

Code: Select all

1

2
q 1 2
q 1 2
AC output:

Code: Select all

0,2
Check input and AC output for thousands of problems on uDebug!

alecassis
New poster
Posts: 10
Joined: Sat Sep 20, 2014 6:36 am

Re: 793 - Network Connections

Post by alecassis » Wed Nov 12, 2014 12:55 am

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
New poster
Posts: 11
Joined: Mon Jan 26, 2015 2:05 pm

Re: 793 - Network Connections

Post by jporcelli1120 » Fri Feb 06, 2015 3:19 am

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
New poster
Posts: 5
Joined: Thu May 21, 2015 9:52 pm

Re: 793 - Network Connections

Post by alekscooper » Thu Jan 14, 2016 6:20 am

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.

Post Reply

Return to “Volume 7 (700-799)”