10147 - Highways

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

Moderator: Board moderators

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

Re: 10147 unclear output format

Post by ishtiaq ahmed » Fri May 02, 2008 8:34 pm

Thanks a lot Sohel bhai
No venture no gain

with best regards
------------------------
ishtiaq ahmed

xique.xavier
New poster
Posts: 1
Joined: Thu Apr 10, 2008 7:41 pm

Re: 10147 - Highways

Post by xique.xavier » Tue Jun 17, 2008 1:29 pm

Hey guys!

Have anyone gotten Accepted on this problem? If yes,could post the solution to I compare with my code?

Thanks a lot!

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Re: 10147 - Highways

Post by viniciusweb » Fri Sep 12, 2008 6:47 pm

What's the correct output for the case below? Thanks.

Code: Select all

1

750
1206 7540
9103 5569
1913 7223
6433 3469
5634 3987
2787 5820
421 498
6362 2928
1839 7243
7615 1035
3816 2136
1837 1591
8546 6903
9463 2935
9251 48
4042 9314
4275 3237
5367 747
2287 6786
8712 2812
4332 2766
4095 5764
5602 1146
8144 3052
6055 7581
5221 4528
2422 3328
5809 9195
1051 7989
1944 8038
4393 4030
5940 8641
496 5528
3979 3481
9385 5199
8594 6468
4877 2263
7199 6178
8009 3542
4458 2009
6207 1009
9442 8613
4032 1900
8277 419
5389 6573
975 7483
2849 7778
5132 6262
5744 4420
5338 1874
1113 4003
5341 9459
8120 3884
275 6263
1019 5158
1020 3348
8931 91
4889 7724
9939 840
6902 7338
5729 660
5595 4356
1488 4608
8139 7304
1692 5835
9005 3071
4200 4347
1516 686
9681 4983
9167 7253
3675 1028
6370 1011
9518 6751
8204 2874
5447 357
742 73
4401 1528
5439 4824
6828 8986
9981 6675
2225 6826
219 7914
2179 3484
9132 6904
2710 1106
9332 6325
3904 6751
9870 4498
4083 4416
7912 5343
3177 1524
8339 1270
5796 9859
3596 6966
5559 5773
6307 7746
3056 1547
4829 7073
5419 4818
4710 262
2693 8945
5574 7241
885 3710
5101 3845
1277 3321
7916 8879
6937 5093
5489 9287
449 4275
7684 5572
3223 1829
4432 1943
2022 3797
8290 3393
3070 9126
2374 5750
7870 8629
9991 4225
3745 6537
5043 5615
4326 2141
1984 6319
6646 3198
8200 216
740 7554
610 2150
7034 703
9698 5934
5341 4970
3694 4498
9235 9212
8170 5591
7621 6156
5615 7550
5380 5428
5689 4986
6441 4554
6069 4800
8551 123
1054 6396
8510 8266
2614 4144
5414 856
7746 6957
5115 3480
9681 1025
3656 5642
3711 268
4377 2325
6493 7190
9358 3127
7296 9657
8233 4517
9652 6756
3157 9137
7930 1717
8518 8914
5 8310
8048 9233
5105 5471
7590 4210
1779 9604
6209 754
8123 7180
4022 5955
3234 450
8967 9005
9111 1752
3375 603
4030 3366
6716 5170
2614 7978
7788 8360
9215 5728
7790 1836
4904 5412
9827 1961
702 436
2680 7664
586 2431
4154 3125
6105 8984
8122 7854
8507 853
3921 4479
3440 2534
4747 8742
6886 5673
3461 9670
3557 937
7815 1762
6343 4599
9767 4837
6744 214
4551 4876
2776 7048
8632 2578
1103 7415
4565 1142
6094 9035
3512 2640
3531 1302
5482 8268
3717 7430
4852 6620
9567 9233
8195 1482
5241 1173
3987 8717
594 7806
7213 3606
5896 8029
5545 6039
3882 952
391 9817
8097 2654
3857 5624
7390 5310
2354 6391
3328 5384
3114 1053
785 6826
4206 4345
5442 7931
1771 7792
8617 949
2574 1171
1425 1170
7957 3471
1920 7125
2995 8439
8815 8775
5900 260
1818 3175
6458 7010
1236 556
2434 3117
8847 7448
2886 4311
6344 2868
6500 996
4069 3561
7029 6569
2896 8337
6756 9859
1464 5037
6785 9687
5990 3528
2155 3482
3595 7308
9052 3533
6379 5420
7122 5837
8077 2065
2019 10
7866 8397
4480 8199
5442 5393
5066 3970
7525 8887
3111 7932
7296 8486
730 5860
2823 2359
3722 1059
25 914
7453 3001
1624 9638
6349 5397
185 7838
6338 9579
5147 9118
6872 3198
6296 5283
7666 5671
9627 1778
7268 5764
1762 2310
9123 6548
8762 7472
9334 9952
408 5807
1935 7361
4364 8781
6130 4096
9937 5911
2677 9103
9519 9911
6486 9974
8145 9176
3492 7445
8229 6188
3807 2557
8325 7687
7069 405
1535 2166
4253 3019
3947 9009
9856 5860
364 8107
5741 5826
7139 4711
2515 146
9370 5065
7559 2990
9626 2843
3420 6979
6013 6596
357 786
9166 3260
4102 2301
8568 9143
4455 1610
6999 8151
5094 956
1635 7238
9448 3221
726 1783
9827 7624
5386 3488
8275 6582
6255 9889
194 1905
921 8686
4053 6273
7795 6496
3811 8045
623 2182
3015 5164
5800 4253
7006 937
5971 4196
266 7217
3690 5603
7371 3960
4672 3932
8793 7666
4648 4
4782 5842
736 9559
1064 6680
1188 8465
4497 7431
9121 7725
6925 6282
3328 1987
8428 2360
6603 7513
2524 7191
9882 7163
464 3377
5124 6822
2805 6216
2991 9726
2379 1524
9120 9863
9288 2264
2274 4412
7440 7731
7636 9872
4568 7319
2177 376
135 8133
1658 7257
6836 9030
7071 4354
170 7358
396 7787
4355 921
5238 1927
1762 9662
9764 3097
8786 7906
5337 7066
7411 4595
4203 730
1257 9899
200 4987
5263 7945
3950 314
6424 9357
4309 5877
8101 4407
2396 1312
8199 6224
4139 7457
7394 8258
5930 4575
7485 8367
5139 7928
4594 6305
2757 4143
7384 2182
709 1422
7579 9404
6059 9540
8127 6413
9527 6880
6152 1980
3913 4161
4910 4078
490 6402
1886 5227
7755 2212
1903 2322
4119 8278
889 6173
7826 2284
8001 9404
3615 1920
96 6491
241 854
1973 7196
5657 8353
1978 5470
881 2474
3287 5818
7445 6774
94 781
2233 3396
9858 8642
9566 1617
1518 2551
3008 7081
7567 2641
3797 1932
6203 6235
4633 4751
1569 728
6516 2214
8 2163
2323 633
8552 3412
7086 6907
6025 6356
9362 5158
7480 7270
485 4257
1745 3054
3923 1595
9123 7047
8050 5610
1029 5685
3548 4714
3939 7330
2627 8555
5188 6376
3641 861
4583 9088
6472 6384
2663 6028
961 2226
7585 3386
3730 1327
2035 8421
6506 7899
4188 1442
5987 3546
5584 2108
5978 9420
1701 6903
6349 3824
6059 9368
8108 7756
6170 8875
6589 7047
5337 3483
794 623
2108 8720
8568 8770
6062 1686
646 2608
9589 1628
8775 7803
9937 9942
2253 2954
7752 8792
8805 5895
3935 248
6215 1540
5824 6782
1521 7642
1251 2619
1607 6660
2922 4365
3413 7543
6574 1381
1065 5401
4504 2300
6504 6119
4229 3124
1212 7953
8287 623
6105 8639
8315 3002
7906 1043
2168 1459
6061 3911
4902 5339
7222 3145
2276 8607
8387 6784
8716 3464
4649 3133
2839 4188
5622 8285
5737 2321
45 5699
5902 3340
8139 5460
6909 6624
5495 8280
4554 4696
6552 6224
2667 5118
534 6604
3411 1746
8784 8439
235 6331
1769 4018
3854 4282
9371 9164
2274 1700
6117 4233
5010 6767
716 1079
9666 3027
4481 2911
6228 136
9788 7659
6519 771
2031 9378
2427 7090
4345 885
9046 1552
1151 2933
8321 2715
93 3777
4014 669
7491 6891
5204 2023
1433 3899
4978 1979
8846 9954
90 4952
9028 6095
5689 7707
9500 8104
2734 4331
4354 5017
7564 6319
4317 7568
2114 5712
718 7069
1036 6022
2121 6700
7859 7425
619 3916
4739 1523
1349 2039
4286 2640
4686 6021
672 2327
1968 7695
2496 8176
9304 8078
7470 5307
6888 7239
5035 895
2672 6493
4801 3773
7290 2023
2053 5777
5418 9873
6587 1770
3504 8067
8299 1880
672 289
3695 3422
3556 7976
5105 8280
2639 7505
8530 2109
1290 6977
691 5488
9641 6501
1052 2756
3180 7761
4876 7674
5722 7232
586 3069
1376 2795
4094 6823
5201 6924
3418 7742
426 3295
6553 7445
5252 9351
5755 9198
7874 5208
8211 2943
748 3537
7903 3153
8755 7727
3112 2283
9603 6509
4484 3968
4353 1342
9397 8987
43 7318
3887 4682
413 9755
728 4559
1430 8336
2675 7927
5687 6145
5995 6500
2147 5114
7569 1712
6688 8453
9597 9096
504 2615
1570 8220
2106 9661
962 5074
6154 263
9093 3288
5814 270
4545 3428
1008 8712
7788 8722
1048 3011
2652 3461
2528 4809
8327 5800
5680 2087
9958 5659
7350 4426
3280 749
4406 6851
5618 6642
1703 2620
4896 6611
4019 6092
9540 3653
6553 4574
6124 3171
7959 2713
5811 4215
9358 3485
2930 4511
264 3016
155 3130
7800 5764
1196 6967
8779 5481
5811 5774
5160 1580
2326 9974
2324 8564
5229 9993
8029 1244
900 2131
9851 2640
3490 8539
2313 5942
4269 8880
3986 1360
1195 8927
3342 4739
9415 2396
1944 5443
5239 5454
224 7469
6029 2622
7090 7902
7275 3506
9213 3812
8866 8209
2826 7785
5087 8050
6426 3313
7785 6264
9153 8792
4395 2492
6361 9504
2267 8175
429 975
8866 5769
1284 9571
1020 6271
8605 9183
5425 1940
3478 2965
8827 9421
8107 6863
8353 99
4312 6849
2243 522
7482 5087
1780 118
7193 7525
8154 3769
9581 7230
2230 4812
784 6943
6848 679
6473 1730
5104 9270
5709 5020
4150 9182
8753 3379
2581 9438
9972 8308
514 4803
2311 7011
3100 9080
5806 4140
962 1659
9469 7038
6333 1843
5475 6881
2838 862
4193 9639
252 231
6727 2067
5748 5733
7736 2249
7898 9399
7599 9235
4479 6000
4777 5234
4272 2247
147 8458
3713 3595
1926 5861
618 7543
5192 5468
6901 2348
8969 307
2080 3450
9595 8096
2840 591
4859 153
5417 7143
8436 8716
8958 1197
1579 4041
3664 7701
4784 6725
50
193 204
389 548
510 233
366 280
269 80
187 375
641 228
518 695
7 27
418 170
693 183
173 654
586 634
289 357
479 27
64 670
650 102
616 458
67 305
668 259
35 616
452 352
582 375
388 576
276 416
427 6
124 118
101 343
147 631
185 155
394 541
666 320
90 30
700 550
284 281
248 59
661 329
128 122
658 479
469 315
165 50
355 541
546 679
45 57
90 45
675 361
13 137
275 691
598 579
423 446

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Re: 10147 - Highways

Post by viniciusweb » Fri Sep 12, 2008 9:14 pm

I got AC!

My output for the case I posted is (please note that the order of the towns may differ depending on your solution):

Code: Select all

1 198
198 46
46 125
125 737
737 210
210 368
368 270
270 82
82 363
363 158
158 734
363 300
1 482
482 225
225 564
225 30
90 600
57 740
45 641
641 481
90 510
233 628
510 132
132 442
233 626
626 529
132 635
481 308
308 617
617 435
435 427
6 451
451 353
641 722
722 374
374 745
745 102
102 590
374 594
594 352
452 663
352 525
525 643
643 205
205 750
650 645
452 416
276 473
473 422
416 563
563 180
563 328
328 126
180 472
472 622
276 177
650 317
317 151
151 14
14 306
306 527
527 372
151 310
310 627
627 66
627 251
45 447
447 48
442 654
173 256
654 275
275 110
691 140
691 407
407 555
256 117
117 631
147 334
631 477
334 217
477 106
477 260
217 22
22 165
50 693
183 464
50 370
370 541
165 644
644 325
355 523
355 384
355 497
384 227
227 85
464 294
541 543
693 459
459 636
636 507
22 382
382 731
731 562
562 339
85 723
723 743
140 341
562 391
543 37
306 664
173 389
548 742
389 387
548 566
389 262
353 570
427 450
450 514
514 490
102 134
134 547
341 222
222 706
706 554
341 655
655 584
251 678
57 15
416 587
587 536
536 632
587 483
483 592
483 423
423 642
446 660
660 501
501 469
315 569
315 208
501 455
642 278
278 405
278 296
296 560
547 224
224 379
379 390
390 681
681 581
390 58
58 589
570 219
222 516
516 402
402 54
54 519
519 411
315 143
143 18
564 283
283 3
3 413
3 9
413 230
9 364
364 316
230 461
461 484
723 221
251 712
712 503
503 433
433 114
114 39
39 229
39 703
703 53
229 603
603 24
24 601
601 74
601 495
74 537
537 216
216 648
555 443
443 488
488 55
55 625
455 687
687 565
565 172
172 615
615 680
680 47
680 179
179 582
375 638
638 366
280 238
280 337
337 604
604 474
474 373
375 302
47 261
261 588
588 595
595 486
486 291
291 250
250 204
193 69
204 445
445 386
386 552
552 343
343 361
101 287
595 749
595 580
580 576
388 49
49 62
49 330
330 649
649 718
649 332
332 524
524 285
285 498
718 5
580 327
388 138
498 462
373 679
679 518
546 478
478 689
689 656
689 2
2 174
69 304
304 436
436 35
458 248
616 213
248 509
213 95
95 301
301 657
657 727
509 647
59 146
638 161
518 141
695 692
692 312
312 157
157 470
470 746
470 232
232 167
167 684
684 609
609 522
522 131
522 206
206 621
161 335
337 344
647 682
682 4
682 123
123 273
582 349
349 533
533 716
716 81
81 19
81 556
349 196
196 424
632 56
56 105
56 602
602 103
602 351
351 596
596 591
596 653
653 652
103 558
224 203
203 512
512 506
506 414
138 192
192 137
137 646
13 502
502 321
321 397
397 385
385 292
502 696
696 164
164 64
670 444
444 130
130 185
155 717
717 115
185 89
89 67
67 223
305 267
185 611
185 521
521 400
267 500
64 557
321 36
537 197
197 20
197 347
347 583
583 577
577 254
254 408
408 728
728 404
684 42
647 8
8 240
110 567
567 218
567 700
550 195
195 428
428 513
250 94
94 307
397 326
326 683
683 133
133 551
394 526
526 688
688 309
309 412
412 419
419 266
309 7
479 380
27 420
420 83
83 249
249 741
27 237
479 148
237 476
27 633
7 178
178 578
178 468
578 76
7 725
249 113
113 520
520 748
748 542
542 51
143 23
339 120
120 160
160 738
738 673
673 135
135 258
160 176
176 499
499 732
555 263
263 282
282 33
33 585
446 244
244 231
221 639
639 169
169 166
639 190
190 448
190 71
71 265
265 214
265 454
454 202
454 668
259 104
259 401
668 457
457 608
608 77
77 313
668 440
401 336
336 607
607 31
336 571
608 199
313 559
199 369
369 534
534 376
376 539
440 43
43 426
426 410
426 11
410 517
517 111
111 346
111 91
91 97
11 311
311 733
733 121
733 149
149 489
149 685
685 561
561 21
121 40
40 112
21 528
528 297
297 491
491 181
491 17
181 170
418 540
170 34
34 242
540 144
528 504
34 735
735 579
598 52
598 709
709 272
52 108
108 599
599 28
28 460
460 463
460 396
396 271
271 686
686 381
504 629
271 322
322 289
357 671
289 245
245 247
28 200
200 182
182 465
465 494
494 32
394 719
719 318
287 713
305 425
750 98
193 88
88 118
124 697
697 139
124 44
44 493
493 184
184 226
260 730
730 395
395 729
729 409
409 159
159 290
497 12
728 393
393 572
451 666
320 467
666 116
467 145
116 553
553 573
573 736
736 65
553 415
415 672
672 403
403 618
618 705
705 634
586 606
606 154
154 73
73 398
398 720
720 704
704 350
606 86
86 279
634 515
154 80
269 252
269 274
720 441
441 84
441 70
515 329
661 574
368 674
674 367
367 610
367 333
500 677
677 211
677 453
558 438
438 109
346 605
605 264
254 175
175 191
191 156
191 619
156 207
207 92
207 662
662 496
496 10
143 61
506 212
94 87
87 593
593 698
698 640
87 119
219 122
128 299
299 286
299 637
628 75
514 345
345 38
345 243
243 511
511 434
38 253
253 277
253 188
574 93
282 508
540 437
395 152
741 234
234 439
329 220
187 449
449 667
667 284
281 288
281 356
356 544
667 711
711 16
711 298
298 209
16 724
437 702
702 359
702 60
60 568
60 348
348 597
597 150
150 466
466 235
348 96
96 456
96 25
327 406
406 257
438 613
613 715
715 378
378 545
359 676
676 314
311 293
293 201
201 186
201 694
152 360
705 358
147 417
62 26
26 99
99 78
99 129
78 136
136 710
1 492
492 29
30 623
623 614
614 342
342 630
630 324
630 669
42 421
421 714
288 475
252 171
171 107
226 747
747 535
535 168
358 142
142 392
392 505
505 239
239 485
485 651
239 549
314 620
468 236
236 68
68 429
55 246
246 63
350 319
319 530
576 665
126 323
323 431
636 399
399 721
721 708
708 575
399 471
471 480
575 726
726 430
726 739
708 487
487 241
241 72
72 41
241 531
41 163
531 707
707 127
127 331
127 295
295 194
713 354
354 189
743 432
432 699
699 362
362 255
255 701
362 303
53 383
383 153
713 624
624 532
624 162
162 371
371 268
268 690
690 377
624 659
381 365
365 79
558 538
690 340
340 612
612 215
75 744
744 100
744 338

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10147 - Highways

Post by stcheung » Thu Oct 02, 2008 9:33 am

I saw many posts about people getting TLE and I can tell you that simple int array and Prim's algorithm is all you need to get accepted.

At first I took advantage of Java and defined some classes and have some fancy data structures like ArrayList. I think I got TLE (3 sec) just from trying to merge the disjoint sets when reading the edges. Then I decided to rewrite the whole thing using primitives only, because I know those fancy data structures add a lot of overheads. Same for STL so for problems like these, don't even bother with Set or Vector etc. I know it's tempting but it only adds frustration at the end.

I think my biggest speed improvement was in how I handled the existing highways in the input. At first I have a disjoint set for each node, then merge them as I process the existing highyways. This is very slow because of all the node "transferring" that happens when I merge 2 sets. So instead I tried something else. First I read all the edges and store them in array. Then I use BFS to find all the connected components. In other words I didn't have to merge the disjoint sets at all. This is simple and fast enough.

After I got all the connected components, I basically just implement Prim's algorithm. Remember to not take sqrt nor store distances in double because it's unnecessary. I have a boolean array that keeps track of which component is already in the MST. After you add a new component to your MST, you will need to update your distance array for all the components not in your MST.

Overall, my Java solution uses 8 int array (some double array). Excluding helper functions, the main code is around 120 lines. It finishes in <0.8 sec. The point is, you can still get accepted with a reasonable amount of code by using primitives only. So forget the fancy STL, Kruskal, path compressions etc.

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Re: 10147 - Highways

Post by empo » Sat Dec 06, 2008 8:45 am

Wrong Answer again and again....,i got accepted in 10397...and this the same question ....why am i getting wrong answer then?..Someone clarify please...Below is my code...

Code: Select all

#include<iostream>
#include<math.h>
using namespace std;

struct grid
{
	int x;
	int y;
	int id;
	double key;
	int parent;
	int in_queue;
}point[1000];

int main()
{
	int T,nop,pre_highways_list,flag,i,j,c;
	struct grid *u,*v;
	scanf("%d",&T);
	while(T--)
	{
		if(flag==1)
			cout<<endl;
		flag = 1;
		scanf("%d",&nop);
		int temp = 0;
		while(temp<nop)
		{
			scanf("%d %d\n",&point[temp].x,&point[temp].y);
			point[temp].key = 20000000;
			point[temp].parent = -1;
			point[temp].id = temp;
			point[temp].in_queue = 1;
			temp++;
		}
		/*Calculating Distance between points*/
		double dis[nop][nop];
		for(i=0;i<nop;i++)
			for(j=0;j<nop;j++)
		{
			int x = point[i].x - point[j].x;
			int y = point[i].y - point[j].y;
			dis[i][j] = sqrt(x*x+y*y);
		}
		

		/*Checking Pre Defined Highways*/
		scanf("%d",&pre_highways_list);
		temp = 0;
		while(temp<pre_highways_list)
		{
			scanf("%d %d\n",&i,&j);
			dis[i-1][j-1]= 0;
			dis[j-1][i-1]= 0;/*
			point[j-1].parent = i-1;
			point[i-1].parent = j-1;*/
			temp++;
		}

		while(1)
		{
			c = 0;
			double min = 200000000.0;
			for(i=0;i<nop;i++)
			{
				if(point[i].in_queue==1)
				{
					c++;
					if(min>point[i].key)
					{
						min = point[i].key;
						u = &point[i];
					}
				}
			}
			if(c==0)
				break;
			u->in_queue = 0;;
			for(i=0;i<nop;i++)
			{
				v = &point[i];
				if((v->in_queue==1) && (dis[u->id][v->id] < v->key))
				{
					v->parent = u->id;
					v->key = dis[u->id][v->id];
				}
			}
		}
		int flag1 = 0;
		double cost = 0;
		/*Calculating Cost of all path*/
		for(i=0;i<nop;i++)
		{
			int parent_i = point[i].parent;
			if(dis[i][parent_i]!=0 && parent_i>=0){
				flag1= 1;
				cout<<parent_i+1<<" "<<i+1<<endl;
			}
		}
		if(flag1==0)
			cout<<"No new highways need\n";
	}
}
"Accepted" is my passion but RTE is my weakness.....

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 10147 - Highways

Post by calicratis19 » Thu Aug 27, 2009 8:27 pm

pls tell me why wa. couldnt find any bug.

Code: Select all

AC
Last edited by calicratis19 on Wed Sep 02, 2009 10:48 am, edited 1 time in total.
Heal The World

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 10147 - Highways

Post by calicratis19 » Fri Aug 28, 2009 5:11 pm

AC.thanks jehad :lol: .
Last edited by calicratis19 on Wed Sep 02, 2009 10:47 am, edited 1 time in total.
Heal The World

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10147 - Highways

Post by Jehad Uddin » Sat Aug 29, 2009 10:18 am

in link function change this if(rank[x]==rank[y])
rank[x]=rank[y]+1;
to if(rank[x]==rank[y])
rank[y]=rank[y]+1;
and in before sorting k=i=1 change ks value to 0
and ur compare function is not ryt for double ;
try to sort a full structure, and it will be easy,

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 10147 - Highways

Post by saiful_sust » Thu Sep 03, 2009 11:06 am

Hi .......
some one plz help me....
I got WA.......... :oops: :oops: :oops:

Code: Select all

Cut after ACC............... :lol:  :lol: 
Last edited by saiful_sust on Fri Sep 04, 2009 4:32 pm, edited 1 time in total.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10147 - Highways

Post by Jehad Uddin » Fri Sep 04, 2009 2:52 am

i just change one thing and got acc with ur code :D :lol: 8)

Code: Select all

  for(i=0;i<n;i++)
      {
         make_set(i);
      }
i changed above one to
to

Code: Select all

  for(i=0;i<=n+1;i++) //to make more safety i have made i<=n+1 i think it will b done in i<=n
      {
         make_set(i);
      }
thoug get accepted ur code is not fast enough,

Code: Select all

 for(i=0;i<n;i++) change it to i<n-1
      {
         for(j=0;j<n;j++) change it to j=i+1
         {
            if(i!=j) // so it will have no work  :D
            {
               a[k].u=i+1,a[k].v=j+1;
               t1=x[i]-x[j],t2=y[i]-y[j];
               a[k].cost = t1*t1 + t2*t2;
               k++;
            }
         }
      }

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 10147 - Highways

Post by saiful_sust » Fri Sep 04, 2009 4:37 pm

Thanks Jehad Uddin..........
:)
and sorry 4 small mistake?????????////
:oops:

agriie
New poster
Posts: 1
Joined: Thu Mar 29, 2012 3:33 am

Re: 10147 - Highways

Post by agriie » Thu Mar 29, 2012 4:02 am

why WA ?? plis help...
here's my code ..

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>


using namespace std;

int parent[100000];

void init(int num)
{
for(int i=1;i<=num+1;i++) parent=i;
}

int find_set(int num)
{
if(num!=parent[num]) parent[num]=find_set(parent[num]);
return parent[num];
}

double distance(int x1,int y1,int x2,int y2)
{
return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main()
{
int T, N, M, i, j, a, b,parent_1, parent_2, done=0;
int nodes[1000][2];
priority_queue< pair< double,pair<int,int> > > edge;
pair< double, pair<int,int> > temp;
//priority_queue < pair <int,int> > buff;
//pair< int,int> smt;

scanf("%d", &T);

while (T--)
{
scanf("%d", & N );

for (i =1;i<=N;i++)
scanf ("%d %d" , &nodes [0], &nodes [1]);

for (i=1 ; i<=N;i++)
{
for (j=i+1;j<=N;j++)
{
temp.second.first=i;
temp.second.second=j;
temp.first= -distance(nodes[0],nodes[1],nodes[j][0],nodes[j][1]);
edge.push(temp);
}
}

init(N);

scanf("%d" , &M);

while(M--)
{
scanf("%d %d", &a, &b);
parent_1=find_set(a);
parent_2=find_set(b);;

if(parent_1 != parent_2)
{
parent[parent_1]=parent_2;
done++;
}

/*cout<<parent_1<<endl<<parent_2<<endl;
cout<<parent[parent_1]<<endl;*/
}

if(done==N-1) printf ("No new highways need\n");


while(!edge.empty() && done <N-1)
{
temp=edge.top();
edge.pop();
//printf("jarak dari %d ke %d adalah : %d \n", temp.second.first , temp.second.second , temp.first);

parent_1=find_set(temp.second.first);
parent_2=find_set(temp.second.second);
if(parent_1!=parent_2)
{
printf ("%d %d\n", temp.second.first , temp.second.second);
//smt.first = -temp.second.first;
//smt.second = temp.second.second;
//buff.push(smt);
parent[parent_1]=parent_2;
done++;
}
}

/*while(!buff.empty())
{
smt=buff.top();
buff.pop();
printf ("%d %d\n", (-1*smt.first) , smt.second);
} */
if(T) printf("\n");
}


//system("pause");
return 0;

}

thanks for help :)

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

Re: 10147 - Highways

Post by brianfry713 » Fri Mar 30, 2012 3:12 am

Doesn't work correctly on multiple inputs.
Check input and AC output for thousands of problems on uDebug!

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

Re: 10147 - Highways

Post by mmfrb » Mon Nov 05, 2012 10:02 pm

why WA? I've tried everything. Thanks for help

Code: Select all

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef vector <int> vi;
typedef pair <int, int> ii;
typedef pair <double, ii> dii;

vector <dii> edgeList;
vector < pair<double, double> > coordinates;
vi id, sz;

void initSet(int n)
{
	id.assign(n, 0);
	sz.assign(n, 1);
	for(int i = 0; i < n; ++i) id[i] = i;
}

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

bool isSameSet(int p, int q)
{
	return findSet(p) == findSet(q);
}

void unionSet(int p, int q)
{
	int i = findSet(p);
	int j = findSet(q);
	if(sz[i] > sz[j])
	{
		id[j] = i;
		sz[i] += sz[j];
	}
	else
	{
		id[i] = j;
		sz[j] += sz[i];
	}
}

double distance(int x1, int x2, int y1, int y2)
{
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

int main()
{
	int TC, n, m, aux1, aux2;
	double x, y, weight;
	int done;
	scanf("%d", &TC);
	while(TC--)
	{
		scanf("%d", &n);
		edgeList.clear();
		coordinates.clear();
		initSet(n);
		for(int i = 0; i < n; ++i)
		{
			scanf("%lf %lf", &x, &y);
			for(int j = 0; j < i; ++j)
			{
				weight = distance(x, coordinates[j].first, y, coordinates[j].second);
				edgeList.push_back(make_pair(weight, ii(i, j)));
			}
			coordinates.push_back(ii(x, y));
		}
		done = 0;
		scanf("%d", &m);
		for(int i = 0; i < m; ++i)
		{
			scanf("%d %d", &aux1, &aux2);
			if(!isSameSet(aux1-1, aux2-1))
			{
				unionSet(aux1-1, aux2-1);
				done++;
			}
		}
		if(done == n-1)
		{
			printf("No new highways need\n");
			continue;
		}
		sort(edgeList.begin(), edgeList.end());
		for(int i = 0; i < edgeList.size(); ++i)
		{
			dii front = edgeList[i];
			if(!isSameSet(front.second.first, front.second.second))
			{
				unionSet(front.second.first, front.second.second);
				printf("%d %d\n", front.second.second+1, front.second.first+1);
			}
		}
		if(TC) printf("\n");
	}

	return 0;
}

Post Reply

Return to “Volume 101 (10100-10199)”