(Challenge) Connecting computers

All submissions for this problem are available.
Chef has decided to start a new software company, the company's building has N offices numbered from 0 to N1 and there's a computer in each office.
All offices' computers should be connected within a single network, so it's required to buy some ethernet cables and hubs. a cable connecting ith office with jth office has cost C_{i,j} also if the ith office is connected with j other offices then it's required to buy a hub with capacity j and this will cost H_{i,j}, note that even if the hub with higher capacity is cheaper than the hub with capacity j the company will still buy the hub with capacity j. Each office should have exactly one hub.
Find a way for building the network so that all offices are connected to each other directly or indirectly while minimizing the total cost, it's not allowed to connect same pair of offices with more than one cable and it's not allowed to connect an office with itself.
Your solution is not required to find the most optimal solution. However, the less cost your solution will provide the more points you will get.
Input
Since the input is large you will not be given it directly. Instead, you will be given some parameters and the generator used to generate the input.
The first line contains a single integer T denoting the number of testcases
The first line of each testcase contains the integers N, C_{max}, H_{max}
The following 2*N lines, each contain two integers Seed_{i,1}, Seed_{i,2} the seeds required for generating the input.
Using one of the generators, C++ generator, java generator, python 2 generator you will get C and H arrays.
Output
For each testcase output N lines, each line contains a string of N characters. if you want to connect ith office and jth office with a cable then ith character of jth line and jth character of ith line both should be '1' otherwise they should be '0'. Note that ith character of ith line should always be '0' because you can't connect an office with itself.
Note that cables information is enough to uniquely determine what hub should be bought for each office.
Constraints
 T = 5
 N = 1000
 0 ≤ C_{i,j} ≤ 1,000,000
 0 ≤ H_{i,j} ≤ 1,000,000
 C_{i,j} = C_{j,i}
 C_{i,i} = 0
 0 < Seed_{i,1}, Seed_{i,2} < 10^{18}
Test Generation
There will be 10 testfiles.
The cost of a cable is chosen uniformly at random between 0 and C_{max} and the cost of a hub is chosen uniformly at random between 0 and H_{max}.
In each of the 10 testfiles there are 5 testcases, the values of C_{max} and H_{max} are:
 First testcase: C_{max} = 40,000 and H_{max} = 1,000,000
 Second testcase: C_{max} = 100,000 and H_{max} = 1,000,000
 Third testcase: C_{max} = 200,000 and H_{max} = 1,000,000
 Fourth testcase: C_{max} = 500,000 and H_{max} = 1,000,000
 Fifth testcase: C_{max} = 1,000,000 and H_{max} = 1,000,000
All seeds in input are randomly generated.
Scoring
You will receive a WA if you didn't follow output format or there is a pair of offices which are not connected.
Your score in a single testcase is equal to the cost of the network outputed in that testcase, your overall score is the sum of scores of all testcases in all testfiles.
During contest you will be able to get your score on first 2 testfiles. After contest there will be rejudge on full tests set.
Example
Input: 1 4 10 20 123456789012 4567890123456 11111111111111 2222222222222 101010101010 2323232323232 112358132134 1928374655647 999999555555 5555559999999 234123124155 1241352352345 234213515123 1231245551223 523432523332 1234124515123 Output: 0111 1000 1000 1000
Explanation
Example case 1. note that the example doesn't follow constraints on T and N and also seeds are set by hand in this sample.
In this example we have the array C:
0 0 7 6 0 0 2 7 7 2 0 7 6 7 7 0
and the array H
9 10 2 0 7 9 0 7 9 3 15 18 10 3 20 5
In the output, first office is connected all other offices and that will make the cost of the network equal to S = 0 + 7 + 6 + 0 + 9 + 3 + 3 = 28, so the score on this testcase is 28.
Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/POINTCN 
Tags  challenge, hillclimbing, kingofnumbers, mst, oct17 
Date Added:  1102017 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions