793 - Network Connections

[raj]

Need Help I dont know Why its """Run Time Error"""

Code: Select all

import java.io.*;
import java.util.*;
class UnionFind{
	int [] rank;
	int [] Parent;
	public UnionFind(int size){
		rank = new int[size];
		Parent = new int[size];
		for(int i = 0;i<Parent.length;i++){
			Parent[i] = i;
		}
	}
	public void MergeSets(int x,int y){
		int PX = FindSet(x);
		int PY = FindSet(y);
		if (rank[PX] > rank[PY]) Parent[PY] = PX; // means py er parent ekhon px
		else Parent[PX] = PY;
	    if (rank[PX] == rank[PY]) rank[PY] = rank[PY] + 1; // 2 ta rank soman thaka means ekta tree er size barano
	}
	public int FindSet(int x){ 
		if (x != Parent[x]) Parent[x] = FindSet(Parent[x]);
		return Parent[x];
	}
	
	public boolean isSameSet(int x,int y){
		return FindSet(x) == FindSet(y);
	}
}
public class Main{
	public static void main(String [] args)throws IOException{
		//BufferedReader k = new BufferedReader(new FileReader("D:/Uva-input.txt.txt"));
		BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter z = new PrintWriter(System.out);
		int T = Integer.valueOf(k.readLine());
		k.readLine();
		while(T-->0){
			int number = Integer.valueOf(k.readLine());
			UnionFind a = new UnionFind(number);
			int success = 0,unsuccess = 0;
			String line;
			while((line = k.readLine())!=null && !line.equals("")){
				StringTokenizer s = new StringTokenizer(line);
				String cheq = s.nextToken();
				int n = Integer.valueOf(s.nextToken());
				int m = Integer.valueOf(s.nextToken());
				boolean l = true;
				//int success = 0,unsuccess = 0;
				if(cheq.equals("c")){
					a.MergeSets(n, m);
				}
				else{
					l = a.isSameSet(n,m);
					if(l) success++;
					else unsuccess++;
				}
			}
			z.println(success+","+unsuccess);
			if(T!=0)z.println();
		}
		z.flush();	
	}
}

[brianfry713]

Try input:

Code: Select all

1

2
c 1 2
q 1 2

[lukai]

I tried various test cases, They all pass. I don't know why I am getting WA?

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
using namespace std;

typedef vector<int>vi;

vi pset(100000),setSize(100000);
void initSet(int N)
{
    setSize.assign(N,1);
    pset.assign(N,0);
    for(int i=0;i<N;i++)
    {
        pset[i]=i;
    }
}

int findSet(int i)
{
    return (pset[i]==i)?i:(pset[i]=findSet(pset[i]));
}

bool isSameSet(int i,int j)
{
    return findSet(i)==findSet(j);
}

void unionSet(int i,int j)
{
    if(!isSameSet(i, j))
    {
        setSize[findSet(j)]+=setSize[findSet(i)];
        pset[findSet(i)]=findSet(j);
    }
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

    int cases,number_of_telephone,success,failure,qcounter;
    cin>>cases;
    getchar();
    string connections;
    while(cases--)
    {
        success=failure=0;
        cin>>number_of_telephone;
        getchar();
        initSet(number_of_telephone);
        while(getline(cin, connections)&&connections.size())
        {
            if(connections[0]=='c')
            {
                unionSet(connections[2]-'0',connections[4]-'0');
            }
            if(connections[0]=='q')
            {
                if(isSameSet(connections[2]-'0',connections[4]-'0'))
                {
                    success++;
                }
                else
                {
                    failure++;
                }
            }
        }
        cout<<success<<","<<failure<<endl;
        if(cases>0)
        {
            cout<<endl;
        }
        pset.clear();
        setSize.clear();
    }

	return 0;
}

[brianfry713]

Try input:

Code: Select all

1

50
c 1 30
q 3 1

[lukai]

Thanks Brianfry, AC . Such a stupid mistake.

[Martin91]

Hello.

I have no clue why I am getting WA's . Please help.

Here's my code:

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;

#define REP(i,a,b) for(int i =int(a);i<int(b);i++)

vector<int> pset(100);
vector<int> rset(100);
void initSet(int _size) {pset.resize(_size);rset.assign(_size,0); REP(i,0,_size) pset[i]=i;}
int findSet(int i) {return (pset[i]==i) ? i: (pset[i]=findSet(pset[i])); }
bool isSameSet(int i, int j) {return findSet(i)==findSet(j);}
void unionSet(int i, int j) {
    if(i==j) return;
    if(rset[i]>rset[j])
        pset[j]=i;
    else {
        pset[i]=j;
        if(rset[i]==rset[j])
            rset[j]++;
    }
}

int main()
{
    int T,st,rac1,rac2,prav,narobe;
    char cq;
    string niz;

    //freopen("in.txt","r",stdin);

    scanf("%d",&T);

    REP(i,0,T){
        scanf("\n%d\n",&st);
        initSet(st);
        prav=0;
        narobe=0;
        while(true) {
            if(!getline(cin,niz) || niz.empty()) break;
            sscanf(niz.c_str(),"%c %d %d",&cq,&rac1,&rac2);
            int i = findSet(rac1);
            int j = findSet(rac2);
            if(cq=='c')
                unionSet(i,j);
            else if (cq=='q') {
                if(isSameSet(i,j))
                    prav++;
                else
                    narobe++;
            }
        }

        if(i!=0)
            printf("\n");
        printf("%d,%d\n",prav,narobe);
    }
    return 0;
}

[Martin91]

Found the error. Thanks anyway

[brianfry713]

That is AC code

[triplemzim]

There is no blank line after the last dataset. So be careful about EOF to avoid TLE.

[dibery]

Another test case.

input:

Code: Select all

10

10
q 5 1
c 4 9
c 4 10
c 9 5
q 5 8
c 8 5
q 1 8
q 1 9
c 3 9
c 1 7
c 1 9
c 1 4
q 10 1
q 7 8
q 4 10
q 10 8
q 8 5
q 8 9
q 6 5
q 5 7

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

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

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

10
q 10 10
c 3 5
c 7 6
q 5 3
c 9 1
q 10 5
c 1 3
q 3 6
q 8 9
c 8 10
c 9 1
c 4 3
c 1 3
c 3 4
c 3 3
c 7 10
c 9 3
c 6 10
q 4 10
c 6 8

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

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

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

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

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

output:

Code: Select all

7,5

2,3

4,6

1,10

2,4

1,7

3,7

3,9

1,7

2,3

[Chuckrute]

Can someone tell me why i got WA?

Code: Select all

Got AC! Code removed!

}

thanks in advance!

PS: I tested every test case in this post.


Edit: Stupid mistake!

[lbv]

Can someone tell me why i got WA?

The output must end in a newline (but not a blank line).

[Chuckrute]

Can someone tell me why i got WA?

The output must end in a newline (but not a blank line).

Thanks!

[apcastelein]

Hello
I've tried several test cases on mine. I'm not sure why I'm getting WA

Code: Select all

I got AC Thanks :)

I've noticed reading through this thread that the input output is of the format

Code: Select all

#testcases

#computers
cmd1
cmd2
cmd3
...

#computers
cmd1
cmd2
...

My code isn't made to handle this but I read through the problem again and I don't see it saying the code needs to handle multiple test cases anywhere. Did I misunderstand something?

[lighted]

Yes this is problem with multiple input.
Old link is not working http://acm.uva.es/problemset/minput.html
See http://www.algorithmist.com/index.php/UVa_793