10034 - Freckles

bitaron · Post by **bitaron** » Sat Mar 01, 2014 8:08 pm

still wa .

brianfry713 · Post by **brianfry713** » Sun Mar 02, 2014 5:20 am

Post your updated code.

bitaron · Post by **bitaron** » Mon Mar 03, 2014 5:53 am

#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>
#include <fstream>
#include <iomanip>
using namespace std;

struct point
{
   double x,y;
};
struct edge
{
   int s,d;
   double w;
    bool operator < ( const edge& p ) const { //overloading operator
       return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
   int c,n,i,j,flag[10000];
//   vector<int>disflag[100];
   double a,b;
//   vector<double>dis[100];
   vector<int>rnode;
   cin>>c;
   for(i=0;i<c;i++)
   {
      double result=0;
   
      cin>>n;
      nodes.clear();
      rnode.clear();
      while(!dis.empty())
      {
         dis.pop();
      }
      for(j=0;j<n;j++)
      {
         cin>>a>>b;
         point temp;
         temp.x=a;
         temp.y=b;
         nodes.push_back(temp);
         flag[j]=0;
      }
      
      int h,k,on=1;
      
       h=0;
      rnode.push_back(h);
      flag[0]=1;
      while(rnode.size()!=n)
      {
         if(on==1){
         for(k=0;k<n;k++)
         {
            if(flag[k]==0 )
            {
               double t=nodes[h].x-nodes[k].x;
                  t=t*t;
               double w=nodes[h].y-nodes[k].y;
                  w=w*w;
               double p=t+w;
                  p=sqrt(p);
                  edge temp;
                  temp.s=h;
                  temp.d=k;
                  temp.w=p;
            //   cout<<"\nrr"<<p<<"  "<<h<<k<<"\n";
                  dis.push(temp);
               
                  
            }
            
         }
         }
         on=0;
         edge temp2;
         temp2=dis.top();
         dis.pop();
         if(flag[temp2.d]==0)
         {
            rnode.push_back(temp2.d);
            flag[temp2.d]=1;
            result=result+temp2.w;
         //   resulted.push_back(result);
            h=temp2.d;
            on=1;
         }
         
         
      //   cout<<"\nrr"<<result<<"\n";
      }
         //   cout<<"\nrr"<<result<<"\n";
      resulted.push_back(result);
      //cout<<"\n"<<resulted[0]<<"\n";
      
      
   }
   
   
for(i=0;i<c;i++)
{
   std::cout << std::fixed;
      std::cout << std::setprecision(2);
      cout<<resulted[i];
      cout<<"\n";
    cout<<"\n";
      
}
   return 0;

}

brianfry713 · Post by **brianfry713** » Mon Mar 03, 2014 11:54 pm

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.

brianfry713 · Post by **brianfry713** » Wed Mar 26, 2014 12:38 am

Input:

Code: Select all

20

17
-2.28 7.23
-2.32 -7.84
-7.21 7.11
-9.76 -8.79
-0.70 7.84
2.42 7.73
-6.86 7.28
-5.75 1.60
8.05 5.41
6.76 4.76
6.11 -9.99
-2.47 -3.22
-8.75 -3.88
0.40 -7.16
-8.34 1.03
-1.75 8.39
6.12 -5.04

20
4.48 7.64
7.88 -1.71
7.59 2.32
-5.27 5.60
4.31 4.87
4.69 1.91
-0.05 -0.29
-3.53 -0.56
-4.45 -4.47
3.06 -1.18
-4.36 -2.76
7.64 1.48
3.14 6.67
-9.52 1.59
-2.29 3.67
1.30 1.99
-9.73 -7.82
0.07 -0.82
-9.66 7.87
-1.70 4.81

9
-7.02 -7.72
2.23 9.94
-3.60 2.42
3.54 7.77
-3.61 0.79
6.43 -9.23
8.41 7.87
-3.42 -1.34
-0.85 0.00

20
6.71 3.28
1.03 1.55
6.30 6.99
0.42 -8.90
1.48 2.21
-3.14 8.72
-8.31 -0.67
-8.45 -7.63
-1.23 4.11
-2.35 4.89
6.86 5.14
-2.87 -6.01
-7.60 4.72
6.87 1.37
-9.49 -2.03
6.82 7.12
-5.77 2.79
-4.66 -6.59
-9.92 6.10
-1.70 5.76

15
0.74 4.47
1.73 6.46
8.02 3.11
7.45 -8.59
-5.37 -1.53
-4.68 2.58
9.72 -1.38
-3.41 5.62
-1.95 1.08
-2.84 4.56
-3.06 -4.84
-5.04 5.52
-9.14 -4.07
-3.99 -8.95
-0.64 6.62

19
-9.91 -3.34
3.96 -4.83
8.76 3.20
-3.79 5.37
10.00 -2.77
-1.88 8.80
4.08 -5.81
0.78 9.31
-2.64 -9.28
-6.55 -4.66
-2.15 -1.91
3.06 8.97
9.83 3.78
9.80 -0.32
4.61 2.02
4.25 -1.49
3.68 0.27
9.04 -1.80
-6.43 2.44

14
9.14 5.24
-6.65 -5.96
8.12 -6.68
4.11 8.24
-4.41 4.41
7.86 5.02
8.44 3.68
-7.70 6.82
2.22 2.22
-2.42 1.99
-3.41 -5.77
8.48 1.66
-4.67 6.87
5.90 -7.76

10
-8.86 -8.62
-9.48 -1.43
-2.50 -9.25
4.44 9.42
-0.91 -4.27
-3.11 -1.16
-3.31 9.68
8.12 -9.44
8.45 9.09
1.30 -4.10

20
1.10 3.48
-9.30 2.59
-4.98 -0.43
1.81 -8.40
4.95 6.50
3.21 -1.23
-5.14 9.09
-7.85 3.97
-6.03 -5.73
-1.06 -2.12
4.77 -1.61
0.65 -1.39
-7.71 0.91
-0.65 -0.27
6.60 -1.81
7.24 5.35
-2.07 -2.31
2.83 7.94
9.55 -1.47
-4.98 -9.79

4
8.23 -1.02
3.84 -5.29
-3.13 -2.24
-2.69 3.68

15
5.70 -7.39
1.23 -4.91
1.57 -3.66
1.65 -0.91
7.29 -9.09
1.83 -1.76
5.94 4.52
-1.97 5.33
-6.15 -1.24
-5.46 -6.86
3.20 -1.13
-7.33 3.52
-2.65 3.48
-9.66 -4.00
3.31 -8.97

17
-5.43 9.22
-3.99 1.33
-7.11 0.92
8.14 5.11
2.39 9.38
1.20 -3.63
7.88 -7.53
-3.93 -3.48
0.38 -7.79
-3.25 -0.79
7.98 4.82
3.06 -9.73
-6.81 1.46
-2.63 4.64
-6.49 9.80
9.02 8.04
-0.64 -1.91

7
2.25 4.58
2.71 5.70
-1.92 -2.81
8.39 9.08
6.96 -3.87
2.20 -5.09
0.86 4.74

7
-8.76 -8.52
7.33 0.53
7.56 -0.12
-5.49 -9.48
5.89 -5.07
-7.04 -1.98
6.11 0.47

15
-3.75 1.07
-3.24 -9.86
-2.66 8.96
3.61 0.42
6.55 -8.71
-8.23 0.56
-9.14 -5.69
6.87 -1.80
-0.55 -7.66
9.68 -7.03
-9.48 9.33
9.41 5.77
1.65 -4.55
-6.01 -2.58
9.11 7.70

7
-9.08 -1.24
5.52 -2.40
4.94 9.89
3.49 -4.07
8.05 1.81
3.58 9.62
-9.53 7.94

5
8.39 4.80
7.77 -3.20
-8.31 8.06
-0.61 3.87
9.32 -8.91

9
-6.70 -5.92
8.76 4.31
-6.94 0.76
8.37 9.69
5.14 4.15
-9.92 -1.13
-9.33 -1.38
-6.20 3.70
1.63 -0.17

9
-8.00 1.61
3.98 8.23
1.86 5.34
-0.80 5.67
2.33 -8.76
7.86 -5.91
-7.04 6.41
0.74 2.16
0.79 3.73

20
-5.06 -2.34
6.53 -8.88
-4.69 -4.98
4.29 2.78
-7.40 -0.89
-5.48 -8.51
-6.51 -0.22
-6.25 -7.26
4.60 4.40
9.18 4.99
-2.69 5.85
-0.73 -6.74
-8.21 9.29
0.02 -8.57
2.22 1.09
8.75 6.01
2.70 7.16
7.75 5.28
-6.38 8.01
-7.32 -2.39

AC output:

Code: Select all

dypbrg · Post by **dypbrg** » Sun Aug 17, 2014 1:08 pm

I have tried all the given input in this thread and my code outputs the correct answers. But when I submit it to the judge, I always get WA. I also already took note of the extra lines needed and that there shouldn't be any blank line after the last test case but i still get WA. What seems to be the problem?

Code: Select all

import java.util.ArrayList;
import java.util.Scanner;


public class Main {
	static int numDots;
	static Node[] adjacencyList;

	static class Node{
		double key;
		boolean visited;
		int data;
		double x;
		double y;
		ArrayList<Node> children;
		Node parent;
		public Node(double x, double y, int data){
			this.data = data;
			this.x = x;
			this.y = y;
			visited = false;
			key = Double.MAX_VALUE;
			children = new ArrayList<Node>();
			parent = null;
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int numCases = sc.nextInt();
		sc.nextLine();
		for(int g = 0; g<numCases; g++){
			sc.nextLine();
			numDots = sc.nextInt();
			adjacencyList = new Node[numDots];
			for(int a = 0; a<numDots; a++){
				Node n = new Node(sc.nextDouble(), sc.nextDouble(), a);
				adjacencyList[a] = n;
			}
			
			//add children to each node
			for(int b = 0; b<numDots; b++){
				for(int c = 0; c<numDots; c++){
					if(b!=c)
						adjacencyList[b].children.add(adjacencyList[c]);
				}
			}
			
			adjacencyList[0].key = 0;
			
			for(int a = 0; a<numDots; a++){
				int u = getMinKey();
				adjacencyList[u].visited = true;
				for(int b = 0; b<numDots; b++){
					double newKey = 0;
					if(adjacencyList[b].visited == false && (newKey = Math.sqrt(Math.pow(Math.abs(adjacencyList[u].x-adjacencyList[b].x), 2.0) +
							Math.pow(Math.abs(adjacencyList[u].y - adjacencyList[b].y), 2.0)))  < adjacencyList[b].key){
						adjacencyList[b].key = newKey;
						adjacencyList[b].parent = adjacencyList[u];
						
					}
				}
			}
			
			double sum = 0;
			for(int z = 0; z<numDots; z++){
				sum+=adjacencyList[z].key;
			}
			System.out.printf("%.2f",sum);
			if(g<numCases-2)
			System.out.println("\n");
			
		}
	}
	public static int getMinKey(){
		int minIndex = 0;
		
		double minKey = Double.MAX_VALUE;
		for(int a = 0; a<numDots; a++){
			if(adjacencyList[a].visited == false && adjacencyList[a].key < minKey){
				minKey = adjacencyList[a].key;
				minIndex = a;
			}
		}
		
		return minIndex;
	}
}

brianfry713 · Post by **brianfry713** » Tue Aug 19, 2014 2:23 am

The outputs of two consecutive cases will be separated by a blank line.

dypbrg · Post by **dypbrg** » Thu Aug 21, 2014 5:20 am

I already have this part of the code that does it.

Code: Select all

 
System.out.printf("%.2f",sum);
if(g<numCases-2)
    System.out.println("\n");

brianfry713 · Post by **brianfry713** » Thu Aug 21, 2014 7:34 pm

See:
http://ideone.com/mXzi7e

dypbrg · Post by **dypbrg** » Sun Aug 24, 2014 2:35 am

ohh I see
if I change my code to this one:

Code: Select all

System.out.printf("%.2f",sum);
if(g<numCases-1)
    System.out.println("\n");

it still outputs wrong answer. see output here http://ideone.com/pT0plI

brianfry713 · Post by **brianfry713** » Tue Aug 26, 2014 11:44 pm

Print a newline char at the end of the last line.

hengbinluo · Post by **hengbinluo** » Sun Aug 09, 2015 8:28 am

ovidiu wrote:You use too small data structures. Just think how many edges can be.

Reading your code I found that after last output there need only one endl and got ACC my code. Thank you!

In my beginner opinion, judging as WA if there are 0 or 2 endl it is a "little" ... unpleasant ...

Agreed. It happened to me too when there was an extra endl for the last case.

OJ Board

10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: 10034 - Freckles

Re: