11228 - Transportation system.

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

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Jul 07, 2007 10:18 am

First thing: construct the graph "on the fly". There is no need to store the edges, since it is a complete graph, and the length of each edge can be calculated using the coordinates of each point.
Then, think about what Prim algorithm does, not how it is usually implemented. The implementation here is in fact easier than normally :wink:

lucastan
New poster
Posts: 10
Joined: Sat Jul 02, 2011 6:46 am

Re: 11228 - Transportation System

Post by lucastan » Tue Aug 23, 2011 6:29 am

I generated all edges for all pairs of cities and then used Kruskal + Union Find (with path compression and ranking)
The union find is less than 10 lines of code
Kruskal done using make_heap and pop_heap

I got WA once because I didn't realize # of states == # of railroads + 1 ........
but why is that so ?
Consider 4 cities:
4 10
0 10
0 20
0 30
0 40

The optimal way is to have 3 roads of 10 units length each.
The # of rail road is 0 but the no. of states is 2 since "0 10" and "0 40" are in two different states !

This problem is wrong, anyone else agree?

btc
New poster
Posts: 1
Joined: Fri Dec 30, 2011 6:45 am

Re: 11228 - Transportation System

Post by btc » Wed Apr 04, 2012 8:03 pm

Hi everyone,
I'm trying to understand this problem, but i don't have in mind the reason of the correct output for some test cases, for example:

Code: Select all

1
77 123
30 52
93 96
89 32
89 70
71 55
40 79
64 10
30 80
62 19
98 67
8 42
57 32
22 27
38 1
52 89
43 74
2 8
82 65
67 20
43 22
95 22
48 16
6 25
86 75
3 96
43 85
93 69
61 4
81 53
84 43
15 20
22 34
26 35
33 28
19 67
19 79
8 45
51 13
86 0
18 68
82 47
16 3
0 80
39 18
5 22
65 26
21 70
66 92
14 65
46 6
21 46
80 32
86 35
67 6
42 29
14 71
55 77
1 3
38 14
82 71
65 41
5 12
3 77
22 67
40 59
48 81
63 63
45 25
78 32
26 83
18 96
45 99
31 56
45 30
80 47
7 1
18 81
the correct output is
Case #1: 1 597 0

But for the condition "For the purposes of this problem, consider that if the distance between any two cities is at most r then they are in the same state",taking in mind the distance between the points (2,8) and (93,96) is 126.589889 that is greater than 123 (r), i think so the correct should be Case #1 : 2 xx yy

Please, tell me what i am wrong.

Thanks

Sorry for my english.

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

Re: 11228 - Transportation System

Post by brianfry713 » Thu Apr 05, 2012 8:36 pm

For this input:
1
4 10
0 10
0 20
0 30
0 40

My AC code returns:
Case #1: 1 30 0

You should assume the problem meant that railroads must be greater than length r.
Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11228 - Transportation System

Post by Scarecrow » Mon Jul 30, 2012 1:34 am

can someone help me with the code please? my code gives the right output for all the I/O given in this thread, but gets WA. Someone help please, I've implemented Kruskal's algorithm here. Once for the individual cities(skipping the inter-state roads), another for the states(considering only the inter-state roads)

Code: Select all

AC.
Never use float as a running variable.
Do or do not. There is no try.

aowal
New poster
Posts: 1
Joined: Thu Oct 04, 2012 11:02 pm

Re: 11228 - Transportation System

Post by aowal » Thu Oct 04, 2012 11:19 pm

getting wrong answer.. :-? . if someone could help,it would be great..thanks in advance

Code: Select all

#include <iostream>
#include <utility>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdio>
#define sqr(x) ((x)*(x))
#define max 500000
#define maxnode 1005

using namespace std;
typedef pair<float,float>ii;
vector<ii>co;

float round(float d)
{
    return floor(d+0.5);
}

struct edges
{
    int s,e;
    float w;
};
edges ed[max];
int par[maxnode];

bool comp(edges e1,edges e2)
{
    return (e1.w-e2.w)<1e-9;
}

int findpar(int x)
{
    if(par[x]==x)
    return x;
    else
    return par[x]=findpar(par[x]);
}

int main()
{
    //freopen("input.txt","r",stdin);
    int t,counter=0;cin>>t;
    while(t!=0)
    {
        int n,r;
        co.clear();
        t--;counter++;
        cin>>n>>r;
        for(int i=1;i<=n;i++)par[i]=i;
        for(int i=0;i<n;i++)
        {
            float x,y;
            cin>>x>>y;
            co.push_back(ii(x,y));
        }
        int c=-1;
        for(int i=0;i<co.size();i++)
        for(int j=i+1;j<co.size();j++)

                {
                    c++;
                    ed[c].s=i+1;
                    ed[c].e=j+1;
                    ed[c].w=sqrt(sqr((float)co[i].first-co[j].first)+sqr((float)co[i].second-co[j].second));

                }

        sort(ed,ed+c+1,comp);
        int s=n;
        float road=0,rail=0;
        for(int i=0;i<=c;i++)
        {
            int u=findpar(ed[i].s);
            int v=findpar(ed[i].e);
            if((ed[i].w-r)>1e-9 && u!=v)
            {
                rail+=ed[i].w;
                par[v]=par[u];
            }


                else if(u!=v)
                {

                    road+=ed[i].w;
                    par[v]=par[u];
                    s--;
                }


        }
        road=round(road);
        rail=round(rail);
        cout<<"Case #"<<counter<<": "<<s<<" "<<road<<" "<<rail<<endl;

    }

    return 0;
}

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

Re: 11228 - Transportation System

Post by brianfry713 » Fri Oct 05, 2012 7:22 pm

Use double instead of float.
Check input and AC output for thousands of problems on uDebug!

Aarya
New poster
Posts: 8
Joined: Thu Nov 21, 2013 6:05 pm

Re: 11228 - Transportation System

Post by Aarya » Thu Nov 21, 2013 6:17 pm

Wrong answer every time:
It passes all the test cases posted here. I can't find the bug. If you can please tell me.
Thanks :(
[#include<cstdio>
#include<cmath>
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>

#define dist sqrt((x-x[j])*(x-x[j]) + (y-y[j])*(y-y[j]))

using namespace std;

struct type
{
int u, v;
double w;
bool operator <(const type& p) const
{
return w<p.w;
}
};

double total_1, total_2;
int no_of_cities, maximum_dist, x[1015], y[1015], parent[1015];
vector<type>data_1, data_2;

int find_parent_of(int r);
void read_input(void);
void determine_connections(void);
void run_mst(void);
void run_disjoint(void);

int main()
{

int test_cases, t=1;
while(scanf("%d", &test_cases)==1)
{
while(test_cases--)
{
scanf("%d %d", &no_of_cities, &maximum_dist);
read_input();
determine_connections();

sort(data_1.begin(), data_1.end());
sort(data_2.begin(), data_2.end());

run_mst();
int k=0;
run_disjoint();
for(int i=0; i<no_of_cities; i++)
find_parent_of(i);
for(int i=0; i<no_of_cities; i++)
if(parent==i)
k++;
printf("Case #%d: %d %.0lf %.0lf\n", t++, k, roundf(total_1), roundf(total_2));
}
}
return 0;
}


void read_input(void)
{
for(int i=0; i<no_of_cities; i++)
scanf("%d %d", &x, &y);
return ;
}

void determine_connections(void)
{
type temp;
data_1.clear();
data_2.clear();
for(int i=0, j; i<no_of_cities-1; i++)
{
for(j=i+1; j<no_of_cities; j++)
{
temp.u = i;
temp.v = j;
temp.w = dist;
if(temp.w>maximum_dist)
data_2.push_back(temp);
else
data_1.push_back(temp);
}
}
return ;
}

void run_mst(void)
{
total_1 = total_2 = 0;
int u, v;
for(int i=0; i<no_of_cities; i++)
parent = i;


for(int i=0; i<data_1.size(); i++)
{
u = find_parent_of(data_1.u);
v = find_parent_of(data_1.v);
if(u!=v)
{
parent = v;
total_1 += data_1[i].w;
}
}

for(int i=0; i<data_2.size(); i++)
{
u = find_parent_of(data_2[i].u);
v = find_parent_of(data_2[i].v);
if(u!=v)
{
parent = v;
total_2 += data_2[i].w;
}
}

return ;
}

int find_parent_of(int r)
{
if(parent[r]==r)
return r;
return(parent[r] = find_parent_of(parent[r]));
}

void run_disjoint(void)
{
for(int i=0; i<no_of_cities; i++)
parent[i]=i;
for(int i=0, j; i<no_of_cities-1; i++)
{
for(j=i+1; j<no_of_cities; j++)
{
if(dist<=maximum_dist)
parent[j] = i;
}
}
return ;
}

]

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

Re: 11228 - Transportation System

Post by brianfry713 » Fri Nov 22, 2013 12:19 am

Input:

Code: Select all

20
87 35211
9263 -9865
-6374 680
9947 7021
-6335 5766
5003 5761
-4544 -493
6843 3305
6601 5419
-8436 -4239
1293 -9761
-4585 3826
5463 6981
-1185 -4686
-4044 4089
8641 5832
9689 -8293
6108 -8377
-7636 -2965
-7200 9775
9257 -3971
9258 -8477
4828 -5288
-9870 9821
-4419 1428
5389 -8305
9242 6874
7576 -9197
-162 8425
6234 111
-337 5794
-8778 4874
-9782 3072
-9894 7330
-9175 -7418
2333 -3372
1872 -9919
-1486 1590
5131 -3300
-8152 -1356
4060 -9289
-8694 7237
-8240 3302
1726 -7398
2713 1598
-2608 -2040
-3446 -7625
5448 -1386
-336 -3228
3076 9275
-377 489
4291 -4592
-9282 -8505
1916 -7196
5170 5849
6560 3764
4722 -771
-3749 -8414
-5812 6482
-1920 -8302
3379 -9379
-7003 9193
-2194 9933
426 -7835
-4840 -8810
1680 -6499
2630 4784
10000 -309
2496 3348
-804 1915
-601 -2335
-9386 -524
1063 -5880
-5677 -3134
-1436 8972
9594 6124
5316 -8058
-4405 -3689
-1524 -6879
-1968 6021
-6758 7357
5861 9712
3124 5872
2940 5860
1495 -660
-9275 -7865
5333 -9106
-1265 -8661
5 15174
-913 3058
-819 -9511
-3848 -1320
4991 -5504
1338 1748
65 35806
-5456 9371
-7198 4732
4324 -9596
9986 5926
-1014 985
6841 1480
6095 -289
1051 2173
-7712 -5170
-8392 -7024
-6534 1376
-9945 790
9007 3339
-4914 5047
-4046 4066
7157 6576
5028 498
4624 9959
9606 -649
-9665 8330
3530 -1409
-7977 -9103
3070 -375
8176 3074
9771 5359
455 9784
4294 -3043
-9704 510
-723 7022
4808 -4618
-8043 8953
3171 1964
5643 -9295
57 -2206
-156 8969
-2440 4113
8731 -2905
6720 3304
-3623 1801
880 8616
-7881 -132
6826 -8666
5565 -9866
7156 7122
-7497 -1437
-2485 5684
-2353 -1818
-1113 -9315
2201 -6711
-7742 -7336
-9502 -7956
-861 3539
-3158 9229
1029 -421
1915 6940
-3193 -4371
-3037 4035
7890 -6368
-9247 -3751
4812 8766
4449 -3022
5160 -7674
-6989 -7905
-895 -2233
432 5212
87 36982
-1378 930
158 3837
-2863 5464
6124 -5092
537 9052
6807 -7069
284 -8779
-2530 4696
7182 4759
-8264 -3998
-1672 1630
3725 -9384
-1617 5060
3993 -7170
7914 8815
3465 4970
2527 -3464
-4280 -2656
5973 -6616
-3843 -8156
-1504 230
1451 -7037
-8620 -7500
7259 -7359
2364 8562
3913 8995
-6669 -9309
9473 -2363
4188 1715
4250 3465
2155 2102
-7642 1436
8780 -1598
1787 -1922
3643 8473
-1298 7944
-5373 -7862
-5361 -6126
236 -3993
-1710 -4382
-5387 -7400
-2988 -7798
3560 1665
-6621 -3516
-6331 1469
-6430 -8650
2786 5824
-5774 -351
7727 5286
3758 6013
3956 1370
7229 -7541
54 8583
-1689 -4412
1207 -9710
-3389 -9679
-3756 9541
1205 3623
-6172 -6476
4993 8306
9656 -2503
-6679 -7717
1932 2441
-2274 1268
1001 3380
-1530 -8517
-2337 -1323
980 -581
8729 -8562
-8272 -6989
-6668 -65
3196 2060
-4318 3297
-9458 -1879
-3574 -490
-9272 5535
-8461 -198
-7758 -5951
9038 7192
4292 3689
5172 38
8715 -7239
5902 -3444
-2006 -306
2706 4630
-1715 3443
-4498 9759
63 37645
3322 4905
-1864 7319
6574 9749
-450 -1136
6634 8113
9026 5514
-798 5671
-4292 3317
9800 -1905
8372 -1857
7837 5701
330 -3635
-6472 4263
4022 8615
-6185 2751
-2345 798
-1884 7137
-9395 5791
-1625 -5311
-3477 3877
-610 -4992
-9322 -731
-7415 -7688
407 107
8250 -3895
-8195 2499
8864 9808
4070 5856
8191 -3888
8863 -1909
-7391 -7995
-7137 -3482
-3971 4446
-7144 -6532
-8935 4405
-6867 -621
-7632 4176
6489 -2467
7640 -5047
1059 616
-6885 9611
9418 6585
2441 -4301
1812 3487
-4701 4352
6358 4395
-9088 1629
-3925 -7059
130 663
-1212 -1069
-7970 1196
-4629 1921
9454 -5602
3072 -4420
6197 -9186
-9576 -2149
-1843 -6968
-1269 9842
7049 -9403
4949 -5737
8659 -3932
7698 5027
7968 -6709
98 24805
6424 1819
-6986 -3538
-7896 -7826
-3428 2106
-8593 -8443
-7629 -6636
1216 7604
-5644 -3484
-3643 9373
-6310 6808
-5208 -2873
3195 -7641
-8893 -6550
462 4613
-7895 -7205
4614 -1863
4599 -7751
-5577 -8652
3455 -9577
-4298 4716
8081 4862
6186 -1927
8311 3017
6110 -5738
-8931 -1612
5515 -6480
-400 -4139
3032 2431
764 707
3503 -6506
5352 2870
5119 1837
3186 3671
4095 -6737
7979 361
-1057 9797
1590 9780
6517 -4872
-610 -100
8289 2626
9867 4180
-6238 7524
3675 -533
-9827 6794
-5992 -5561
-8971 7397
-766 9360
3031 9869
-6869 -3860
6501 -2875
642 -5169
-5390 -4557
4292 -7769
2132 -8873
7474 -2598
-8419 4141
5385 7341
528 -4657
-4142 -940
3499 701
1819 -134
-774 8249
8117 -5227
913 -4023
3102 -8752
-200 -2587
2856 -6257
-305 4410
9258 868
8270 -4453
-6592 -9548
-8487 9851
-1085 8794
-2147 2041
-3538 4773
-5362 -4928
-2959 8281
-6947 7585
-6439 -4843
126 3966
-4901 6663
-5874 9926
8057 -8325
2543 7543
-6911 7314
-8514 812
4384 -3502
-988 -7001
5040 -6702
8071 6865
-4343 -8498
-6497 -3571
-5986 2698
-8425 -3443
-5757 -2425
-2041 1702
1627 -657
4739 5806
95 39912
718 -2718
-8186 -9842
377 2204
8925 6198
9496 9389
9974 3964
9187 -8714
1437 -4370
-7952 -7310
2968 5451
-3254 -2656
9046 -9069
3995 8426
4232 4394
-5924 -1266
9737 1300
5179 8515
4440 -8450
-8531 -4445
-5057 3364
1048 -5315
-4028 -5084
4267 235
6646 7409
6580 6315
-2620 3334
7986 -6675
-8249 -3575
-9182 1981
-5565 9704
4724 -1384
851 -5829
-558 -97
5458 -4710
-7626 911
5597 -9599
-4683 3423
-2622 -4711
-7303 9585
9620 -2256
-5202 -7003
-3678 -3001
7146 -7217
4764 1794
5218 -8316
300 -7081
-2910 -58
-6435 -5128
162 -9747
1164 9023
-6856 6258
-320 481
5770 -1538
1767 7058
-1478 -7813
-4816 1386
-7894 3320
6103 5228
742 9252
-9065 4588
7507 -319
9623 4957
-6451 -5403
-1429 -3092
-4070 7432
3689 9735
3937 -925
-8743 -6632
-5854 -294
5615 3024
-1870 2668
-4013 -9202
9747 3957
6929 -4189
-9602 4210
-6110 7865
6542 7905
-3778 -2767
4141 -9910
7522 4793
8249 -9930
2866 1211
8300 2185
-4389 4123
867 -3833
8835 -8775
-4255 -7282
6675 -1457
8075 -788
-6579 3604
5189 8473
-9903 -2689
8265 5451
9262 41
-1446 2405
82 1208
1714 -3198
-7293 2783
627 3735
9902 2040
6986 -8507
-2068 -7544
4720 -7270
1943 -1672
-8069 2794
1266 9085
117 -9160
-9989 5085
-4875 -1619
-5493 9273
9776 3679
-5798 -9297
3486 1490
-1055 -3091
-7331 -5888
-673 -1154
1302 9656
-7615 7259
-693 -3978
8816 8049
-9146 4959
5799 3803
2608 4692
-3207 9531
8803 7733
1411 1300
5724 8579
3789 9334
-36 2931
-9237 -3546
5300 2633
2288 3811
4791 322
6344 8395
-9837 -5903
9057 8881
6404 -5262
9430 8576
8107 -989
464 -3777
7523 6909
9208 -8126
-5071 6968
-102 6717
-6830 4893
-2475 661
-5528 -7810
2513 -6466
-8072 9263
-6641 2577
5178 -4188
551 -3864
-5288 1581
-5688 -20
9924 -7182
-6553 4776
-9629 7447
4414 -3624
-6908 -4700
-9808 -1968
-7587 -16
2174 1438
4972 606
-132 -1593
-9016 -9380
-3567 6949
-6916 6162
1464 -9296
4405 1517
4335 5776
552 4329
1775 7783
-5842 923
9944 -91
-8339 971
-5325 -9865
1573 -5926
4681 6850
54 26632
886 -1731
-1062 3682
-156 -8961
-8257 5744
-2740 -4972
-9197 6149
477 -8405
-6902 5076
-4002 -4028
9602 977
-8053 -4059
-203 -8738
-943 -3377
-2807 -4909
5357 -6263
2007 9891
3573 -37
1003 -5335
-9592 -6584
-1556 6467
2615 -2331
2985 2968
-1956 -3188
6505 9804
780 7763
-2575 6106
-8912 6448
-3209 7222
-3967 146
3883 3984
7596 -8611
5074 -390
4276 1168
8305 -3924
-7458 8405
-3927 469
-6564 8879
-4310 -7222
-7419 5201
2964 -4084
-7979 3361
3530 -5891
-4949 -6890
3256 -9680
8026 1085
6195 859
-5810 5621
-3212 1268
7344 -7814
-9410 -4908
5561 -6393
-3794 385
3163 -7283
7919 5617
89 13511
6547 4603
8712 -6446
385 76
397 -6238
8568 -2639
-8060 -1578
-5958 4763
-3970 -3870
-1684 4551
9643 -2905
4423 2628
-6988 8924
-8360 -9372
6245 9896
9361 -6721
-8398 7778
-4948 5908
-4017 -9687
-2203 9158
-3482 -9900
-1478 -3636
-5153 2179
8310 6285
835 4599
-4586 346
-3306 477
3121 9837
-5815 -294
-398 8483
-4518 -9571
-8073 2683
2311 -2915
1119 700
3578 -7985
-7885 -7364
2722 -6184
5996 4359
643 7569
2167 8026
-1629 -8522
5676 7581
-8863 5066
-1508 2518
1000 -4678
-527 -8186
4498 6482
-2713 5121
-458 -3192
-1177 8407
-8958 -6881
-3064 4660
-982 3764
5054 -7069
-9044 9661
-5141 -2780
-1478 3048
1834 -9465
6774 3380
8703 -9674
-4139 -2227
-2025 1896
737 -5921
4609 5263
3669 -9722
-2881 -6569
-8189 8432
2196 7776
-9294 829
4211 -2751
8190 -4617
-7849 9070
-6675 432
-6188 3986
8033 -9902
1592 -3765
-8149 -6107
-2027 9568
4830 2588
6588 -7419
-267 2219
650 -6294
-8519 1545
-3906 -3434
7536 -4092
5012 -9696
9375 5726
-122 7163
4869 -3580
-3481 3690
86 9591
-9485 8111
-8602 -4504
8085 -1512
4790 6228
2167 8393
-7902 -1757
-6492 -7183
3104 -2700
6929 -397
3628 640
86 1940
-898 6723
-6857 9964
7375 -6029
-9408 3383
5214 -8981
-3484 -8893
3316 6613
2840 -1679
-3287 1826
-9931 -4993
1545 2532
9832 -6423
6901 -5352
9009 -9520
2420 529
-2749 -906
2779 -4758
2934 4115
-2503 153
4893 3527
8355 -7289
-6956 -8592
3450 5392
-2783 5884
-5389 -9838
2694 -2714
4585 9877
-1754 6246
6726 5206
-4266 975
-9931 2866
8109 6707
4542 6569
442 4763
2010 -4240
-1529 -4666
464 365
-4244 1515
1119 -6087
-5924 6694
-2299 9452
-6952 -9510
-9543 -7715
7491 1294
-7731 -9097
3770 -3054
-2627 -3941
-3652 5599
361 -8086
-2326 6790
-7877 -7629
6457 9866
5101 2587
-9779 -4067
-7374 -59
-608 -1982
2229 4048
-9947 2440
-2545 2686
7311 -8735
-1789 3445
9504 4801
4120 9305
-8782 -4149
-3639 -5520
572 2614
6200 2205
-1487 749
6682 1301
-8759 -1266
6752 -6971
7077 4354
514 -1020
-4613 7131
8396 -8311
11 15237
-8782 327
3352 8358
-2071 5338
-6462 8291
904 4290
-3505 4111
-1420 -2896
-7875 5008
-6259 -4738
2012 -2913
-4839 -5787
39 1428
-61 5675
7365 -3979
2439 2055
-3898 6219
4577 3657
2715 9454
7745 -7495
-9484 6254
4085 2369
-6807 -2989
-4261 -7336
1647 -961
6126 3201
7414 -6342
6468 -8714
-9318 8048
-5931 127
-4097 8047
4265 6508
3886 2005
5180 -1159
5068 -3400
-7147 6645
2734 5584
-3685 6938
-6677 5928
-5034 2054
-4746 4970
-7651 -5187
-3901 -3612
-1844 8817
2664 -3219
-1452 2225
2454 8567
4293 -3466
9096 -3661
6660 3193
-163 4163
3467 9514
26 5775
-7782 9782
1835 -2785
-7815 906
5719 -9191
918 -5466
-2929 -8183
2320 9075
5020 9735
-7978 -5412
1122 1194
7533 6315
3228 218
-1899 7914
-8853 -6936
-645 -8432
-8651 -8682
2255 5295
-3800 6906
-8565 4440
-7306 -8082
-2544 6075
8870 -235
-501 -6504
-1915 3889
-4917 5242
1556 9207
9 35522
-5751 -1496
1568 7526
-7186 -883
4157 -5356
-6341 -5837
-5211 -3589
-9150 -141
5498 -54
-3980 -6456
57 18154
-3550 -5111
-7502 249
-4509 4535
7462 -2419
7639 -9233
-728 607
-1868 -4392
4726 -5440
2925 4667
8830 -1118
5293 6584
-3558 -2660
7286 9864
-2872 -8061
-1386 -6695
1915 -5843
8127 5064
3319 4413
-8006 -6383
-5615 780
-8614 -6647
-1039 3657
-8063 3239
-2095 -2593
6289 4863
1446 456
-8484 5302
5165 -8391
-6452 8802
-4173 -3987
3891 2162
946 7742
5875 2018
5635 -5736
8766 7869
-5058 -6260
-8883 -6128
-9168 7625
-4969 -6945
7918 -1263
-7087 -4959
-9658 -637
4693 -1850
672 9229
-4759 8242
4124 6499
7961 9133
4871 -1209
6776 3836
5425 505
4246 5541
-6866 -5912
-8288 9084
-7862 -6034
6424 -3257
5505 -6224
6861 9338
53 33582
8797 1553
-206 -8120
8379 -2242
611 -2361
6430 -9940
7617 -4519
9708 3205
2467 6762
-9151 7674
6757 5601
9567 -7439
3026 8896
-7329 5990
9048 -1470
-1902 9532
1085 256
2136 -3106
8374 -5401
2238 4235
8016 -1016
4466 2388
-4407 5632
2394 4173
1846 -8220
7381 3243
9526 -1398
1218 6947
2936 2551
-5199 7611
-9138 1984
-4040 2900
-6486 5668
-9733 8096
2330 -8113
872 6226
2335 346
-302 -942
-6770 -8352
-6572 -4188
-7224 8797
1119 -9192
7755 -7699
8573 -3942
-2611 4411
115 -2906
9994 -1749
-6081 6075
7891 -2771
-884 -2093
-2147 3942
-5713 -6292
2766 -9813
-8165 7706
87 9060
-7767 -1016
-208 -3706
2316 3353
-6869 1267
-4322 888
-8298 520
8771 9514
9310 -8304
-1075 -3590
8038 7200
1141 -8239
-4530 -4109
-201 9149
6855 -8044
-8327 5356
-5661 -5907
387 -6094
-9021 4132
-881 -7298
7311 -5890
8351 4797
8032 9013
-5571 7122
-2748 7341
4540 7075
8837 -4710
4902 -4319
-1450 -1973
-17 -5300
-9945 -4596
-503 1656
9284 -1884
-7753 -6396
27 -9738
-1906 5087
3605 1058
3792 -3556
-2714 1636
-1024 8221
9017 8260
-2730 -2764
6638 -8427
-400 -7829
592 -4812
4313 -6697
8681 648
-7516 -2469
1135 7964
-8054 -1548
-6462 -8838
2220 3761
-6074 7143
-1222 -3989
-2047 1212
3192 -8526
2432 -3031
2263 -9539
-7368 -931
7978 -8138
-1114 3225
-2407 2291
9822 -2434
-4471 77
8529 4677
5839 1197
-5043 -4213
-7070 1780
-8489 -1117
-6184 5429
6904 3185
-9847 7008
-8810 3056
-7876 2416
7999 -6178
-9233 -6177
6114 -3115
8172 -1640
-7843 9656
4332 -2578
8619 -5594
194 3892
-608 -2704
9901 3124
-1448 903
-5912 -2563
-1835 -824
-7769 -2038
46 8086
3178 -1923
1900 -4182
6424 3945
-3974 1734
5110 4596
-7983 -1817
2590 3162
774 -5644
1652 -3496
9628 -9835
4790 5273
-7291 1900
-5203 -7402
4281 875
-9771 -2972
8826 -7900
-2081 3407
1073 725
-3821 -1937
-3621 -9181
2723 -8712
8172 -1604
2752 -967
5537 -1055
2832 -1875
-6603 8885
785 -2379
3940 -3893
6982 5582
-3670 -1780
321 -9069
8060 -1123
9602 -8040
3744 2853
3672 -498
4511 -9877
-1481 -3606
5428 2682
-4652 -5008
6838 964
3570 8180
-479 -6045
62 -5646
-6344 -6540
5401 764
5417 3707
46 4787
1402 3476
-3672 -4094
5408 -4854
-4731 10000
114 3639
-3679 7509
-3779 -738
-6053 1669
-152 -3221
735 7517
-8130 9369
-3451 -5483
9003 -753
-7047 -8051
1392 4419
-2106 -742
5164 -7207
1660 7943
-8338 4292
-2070 -9351
-8121 1776
-8962 7972
-360 -1900
4880 -5015
-7499 -6792
-3703 -665
3852 -1908
7339 2846
8517 2854
-2728 -5988
6991 -92
6422 8887
6829 2154
-3555 1803
2452 8491
267 8097
6068 8052
-127 5026
-9990 -571
2637 -5248
7808 -3768
4324 -7345
9222 1659
-5487 5383
-6885 7738
1366 5506
AC output:

Code: Select all

Case #1: 1 134713 0
Case #2: 1 23053 0
Case #3: 1 117802 0
Case #4: 1 121832 0
Case #5: 1 103712 0
Case #6: 1 135367 0
Case #7: 1 138590 0
Case #8: 55 20976 110802
Case #9: 1 96654 0
Case #10: 1 128809 0
Case #11: 1 130578 0
Case #12: 1 37926 0
Case #13: 29 8774 65807
Case #14: 2 68802 6077
Case #15: 1 32996 0
Case #16: 1 100059 0
Case #17: 1 93271 0
Case #18: 1 125813 0
Case #19: 1 88591 0
Case #20: 1 91707 0
Check input and AC output for thousands of problems on uDebug!

Aarya
New poster
Posts: 8
Joined: Thu Nov 21, 2013 6:05 pm

Re: 11228 - Transportation System

Post by Aarya » Fri Nov 22, 2013 8:51 am

Thanks Brian fry for replying.
I see my bug was in determining the number of states. At first I assumed that "if distance between two cities is greater than r then theys are in different states". But seeing your accepted output I changed it to "if distance is greater than or equal r then they are in different states". Then I ran my code and it gave same output as yours :lol: . Then I ran my code against the I/O thread posted here previously, it produced Wrong Answer :oops: . I got tangled but I submitted my code once again and got a Wrong Answer :evil:
Thanks once again.

Code: Select all

#include<cstdio>
#include<cmath>
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>

#define dist sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))

using namespace std;

struct type
{
    int u, v;
    double w;
    bool operator <(const type& p) const
    {
        return w<p.w;
    }
};

double total_1, total_2;
int no_of_cities, maximum_dist, x[1015], y[1015], parent[1015];
vector<type>data_1, data_2;

int find_parent_of(int r);
void read_input(void);
void determine_connections(void);
void run_mst(void);
void run_disjoint(void);

int main()
{
    //freopen("output1.txt", "w", stdout);
    int test_cases, t=1;
    scanf("%d", &test_cases);
    while(test_cases--)
    {
        scanf("%d %d", &no_of_cities, &maximum_dist);
        read_input();
        determine_connections();

        sort(data_1.begin(), data_1.end());
        sort(data_2.begin(), data_2.end());

        run_mst();
        int k=0;
        run_disjoint();
        for(int i=0; i<no_of_cities; i++)
            find_parent_of(i);
        for(int i=0; i<no_of_cities; i++)
            if(parent[i]==i)
                k++;
        printf("Case #%d: %d %.0lf %.0lf\n", t++, k, roundf(total_1), roundf(total_2));
    }
    return 0;
}


void read_input(void)
{
    for(int i=0; i<no_of_cities; i++)
        scanf("%d %d", &x[i], &y[i]);
    return ;
}

void determine_connections(void)
{
    type temp;
    data_1.clear();
    data_2.clear();
    for(int i=0, j; i<no_of_cities-1; i++)
    {
        for(j=i+1; j<no_of_cities; j++)
        {
            temp.u = i;
            temp.v = j;
            temp.w = dist;
            if(temp.w<maximum_dist)
                data_1.push_back(temp);
            else
                data_2.push_back(temp);
        }
    }
    return ;
}

void run_mst(void)
{
    total_1 = total_2 = 0;
    int u, v;
    for(int i=0; i<no_of_cities; i++)
        parent[i] = i;


    for(int i=0; i<data_1.size(); i++)
    {
        u = find_parent_of(data_1[i].u);
        v = find_parent_of(data_1[i].v);
        if(u!=v)
        {
            parent[u] = v;
            total_1 += data_1[i].w;
        }
    }

    for(int i=0; i<data_2.size(); i++)
    {
        u = find_parent_of(data_2[i].u);
        v = find_parent_of(data_2[i].v);
        if(u!=v)
        {
            parent[u] = v;
            total_2 += data_2[i].w;
        }
    }

    return ;
}

int find_parent_of(int r)
{
    if(parent[r]==r)
        return r;
    return(parent[r] = find_parent_of(parent[r]));
}

void run_disjoint(void)
{
    for(int i=0; i<no_of_cities; i++)
        parent[i]=i;
    for(int i=0, j; i<no_of_cities-1; i++)
    {
        for(j=i+1; j<no_of_cities; j++)
        {
            if(dist<maximum_dist)
                parent[j] = i;
        }
    }
    return ;
}



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

Re: 11228 - Transportation System

Post by brianfry713 » Fri Nov 22, 2013 9:50 pm

On my machine (linux using g++) your code doesn't match the I/O I just posted.
Check input and AC output for thousands of problems on uDebug!

Aarya
New poster
Posts: 8
Joined: Thu Nov 21, 2013 6:05 pm

Re: 11228 - Transportation System

Post by Aarya » Tue Dec 03, 2013 7:06 pm

Thanks Brian fry for your brilliant test cases.

Now got AC

HiWOOOORLD
New poster
Posts: 1
Joined: Fri Feb 28, 2014 10:06 pm

Re: 11228 - Transportation System

Post by HiWOOOORLD » Fri Feb 28, 2014 10:10 pm

Code cut after AC

Thank you brianfry713, I hadn't seen where i have used float.
Last edited by HiWOOOORLD on Sat Mar 01, 2014 5:05 pm, edited 1 time in total.

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

Re: 11228 - Transportation System

Post by brianfry713 » Sat Mar 01, 2014 12:26 am

Try using double instead of float.
Check input and AC output for thousands of problems on uDebug!

Shajal
New poster
Posts: 1
Joined: Wed Jul 06, 2016 8:18 am

Re: 11228 - Transportation system.

Post by Shajal » Wed Jul 06, 2016 8:24 am

Someone please help me.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define MAX(x,y) x>y?x:y
#define MIN(x,y) x<y?x:y
#define MAX_VAL 1009

class base_class{
struct stru{
int index;
double cost;
bool operator<(const stru s)const{
return s.cost<cost;
}
stru(int x,int y):index(x),cost(y){}
stru(){}
};
std::vector<std::pair<int,double> > ad_g[MAX_VAL];
std::priority_queue<stru> pqe;
int x[MAX_VAL],y[MAX_VAL],vis[MAX_VAL];
public:
int n,r,state;
double rail,road;
void initializ(){
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(vis,0,sizeof(vis));
}
void input_fun();
void prim();
};

void base_class::prim()
{
std::pair<int,double> pi2;
stru pi;
road=rail=0;
state=1;
pqe.push(stru(1,0));
while(!pqe.empty()){
pi=pqe.top();
pqe.pop();
if(vis[pi.index]==1)continue;
vis[pi.index]=1;
if(pi.cost<=r){
road+=pi.cost;
}
else{
state++;
rail+=pi.cost;
}
int si=ad_g[pi.index].size();
for(int i=0;i<si;i++){
pi2=ad_g[pi.index];
if(!vis[pi2.first]){
pqe.push(stru(pi2.first,pi2.second));
}
}
}
}

void base_class::input_fun()
{
int d,i,j;
scanf("%d %d", &n,&r);
initializ();
for(i=1;i<=n;i++){
scanf("%d %d", &x,&y);
}
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
double a=x-x[j];
double b=y-y[j];
double d=sqrt(a*a+b*b);
ad_g.push_back(std::make_pair(j,d));
ad_g[j].push_back(std::make_pair(i,d));
}
}
}


int main()
{
int t,casee;
scanf("%d", &t);
for(casee=1;casee<=t;casee++){
base_class bc;
bc.input_fun();
bc.prim();
printf("Case #%d: %d %.0lf %.0lf\n", casee,bc.state,bc.road,bc.rail);
}
return 0;
}


Why getting WA

Post Reply

Return to “Volume 112 (11200-11299)”