1218 - Perfect Service

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

Moderator: Board moderators

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

1218 - Perfect Service

Post by brianfry713 » Sat May 25, 2013 2:12 am

Input:

Code: Select all

971
574 355
125 574
40 125
687 40
394 125
202 574
607 355
365 574
856 574
263 856
603 687
918 394
709 394
438 709
774 607
84 40
746 574
249 856
72 438
659 746
70 603
507 574
345 249
738 249
265 856
224 125
408 263
409 202
310 365
281 265
488 409
907 918
675 687
50 574
217 675
152 355
610 70
538 70
796 675
247 687
2 408
847 281
499 659
349 50
255 50
743 281
368 538
558 365
568 125
95 50
56 2
852 499
420 56
287 345
241 409
415 796
148 574
254 408
559 249
132 603
9 249
370 72
166 249
453 746
804 224
396 125
474 659
964 396
865 538
333 675
20 50
458 70
211 420
327 559
919 796
487 370
168 919
29 349
662 396
120 168
24 50
823 507
777 607
246 499
925 918
402 709
761 409
11 408
697 249
673 70
63 24
119 168
495 249
326 687
93 310
444 603
250 11
54 746
943 310
605 70
210 211
949 255
728 265
248 355
828 453
45 574
768 132
102 949
951 255
742 148
757 355
110 796
958 607
941 474
432 368
830 919
586 568
725 907
956 247
920 365
578 432
945 925
172 499
504 951
204 507
785 217
51 255
942 725
663 761
251 785
571 865
392 50
714 349
43 95
322 949
506 907
215 942
853 394
417 742
69 24
41 20
378 168
595 687
371 687
107 663
177 956
236 504
284 907
294 204
410 852
206 410
479 738
769 294
665 488
96 852
797 236
689 675
290 586
55 215
289 785
947 823
262 119
680 947
723 499
706 392
191 217
459 177
332 742
631 559
434 847
519 102
500 45
701 84
529 956
476 507
473 687
278 294
888 856
73 742
86 458
352 697
89 725
602 605
188 352
547 24
121 204
511 504
464 294
870 86
641 72
661 757
8 602
614 738
385 394
521 327
867 409
25 50
17 417
655 20
324 89
320 947
625 856
525 746
553 663
253 11
221 326
775 949
570 499
899 525
283 73
433 823
657 11
893 689
170 602
259 8
48 17
21 742
190 663
794 487
534 177
720 265
44 202
873 51
650 324
613 828
644 738
513 224
756 570
182 506
131 248
883 20
28 689
80 586
497 255
382 188
884 417
196 941
954 534
556 54
628 644
235 110
82 709
810 459
936 246
691 255
629 487
616 224
127 797
94 131
293 775
360 464
218 797
535 177
837 614
171 538
256 320
493 907
921 333
669 603
257 519
157 24
401 96
341 568
844 235
766 507
860 310
937 132
592 629
467 709
580 290
537 853
524 919
226 332
461 907
882 687
5 521
717 110
466 29
960 44
579 43
696 382
747 433
779 797
551 56
359 856
552 603
874 578
683 247
901 206
192 341
815 964
213 44
76 352
411 579
678 662
158 382
339 72
906 433
546 132
564 919
792 810
916 40
88 69
161 218
12 464
711 937
880 339
755 794
486 580
896 131
139 417
1 341
216 592
379 613
690 696
654 815
871 579
343 438
71 571
167 844
877 796
468 95
805 410
276 678
670 343
137 25
77 882
763 579
567 595
544 678
752 873
100 574
6 556
671 495
840 595
543 571
565 553
108 723
412 382
583 191
376 45
876 8
824 224
16 696
492 107
729 610
640 564
798 401
298 586
910 876
966 265
185 8
563 535
961 701
533 320
827 182
676 556
425 687
38 595
875 628
163 920
428 628
699 559
451 662
98 586
681 444
318 226
140 519
481 559
851 804
898 166
924 451
198 121
207 605
557 12
969 661
831 378
866 281
928 942
430 262
817 125
698 828
498 556
230 602
688 654
4 385
863 964
895 107
354 683
822 148
351 210
833 504
264 467
338 717
316 402
391 333
422 45
421 84
572 551
788 659
201 882
126 76
858 579
31 276
175 77
388 5
367 659
694 72
353 333
618 170
727 595
878 680
362 157
15 177
101 709
523 211
296 320
114 140
423 316
502 538
885 500
786 287
227 249
686 884
393 95
934 132
577 73
270 681
109 880
475 775
186 262
968 898
634 126
703 519
268 410
33 453
303 538
128 547
601 796
243 729
733 565
849 84
456 840
439 88
685 570
176 38
470 4
414 747
624 899
36 733
712 333
780 248
619 960
142 960
53 921
811 521
948 657
955 281
78 703
869 298
59 191
282 644
164 804
328 867
615 875
309 95
829 644
203 574
195 498
344 831
800 53
437 54
767 94
842 362
317 410
118 48
617 368
130 487
386 257
445 822
116 878
903 798
106 98
275 817
730 195
383 41
622 29
719 235
61 78
510 466
561 249
835 371
292 411
144 757
930 316
807 70
693 444
485 937
679 359
299 411
656 256
912 476
522 298
926 502
37 412
194 867
591 20
350 320
460 392
652 108
707 76
494 293
397 142
68 800
477 20
667 241
825 871
81 401
193 743
531 667
85 941
329 556
891 284
273 895
944 954
582 655
22 829
312 196
542 628
587 523
405 101
540 68
398 966
509 522
514 29
319 284
664 116
795 896
660 1
60 898
156 6
872 660
279 275
913 926
151 675
783 699
34 196
260 206
576 780
245 28
818 69
612 603
879 534
744 445
527 564
770 817
231 486
124 128
228 660
179 360
626 433
496 874
448 625
471 926
566 641
647 142
931 514
705 388
150 794
962 161
803 944
240 473
134 657
209 101
599 537
905 246
749 417
606 179
581 624
754 899
854 376
153 44
776 139
27 456
117 788
138 656
342 202
684 498
183 610
387 684
741 943
26 654
505 882
315 275
74 547
638 227
390 928
52 678
745 385
597 398
238 522
927 951
922 4
297 873
726 157
187 125
611 763
806 665
929 581
739 283
374 829
573 652
750 293
967 901
286 656
864 412
787 344
416 151
635 743
890 587
819 669
237 231
674 316
526 191
902 725
892 533
155 31
838 59
900 41
381 432
897 290
555 686
104 415
450 743
64 27
940 109
212 326
455 299
305 55
841 132
87 84
859 41
443 510
938 294
288 31
146 2
97 673
441 359
205 5
952 438
554 451
799 34
214 338
731 835
311 595
178 487
356 95
736 822
424 882
267 952
646 615
304 5
280 907
734 565
244 376
446 743
242 146
399 644
682 755
839 416
484 132
608 948
737 495
252 44
442 297
753 634
816 948
639 355
348 612
633 55
751 949
939 86
789 537
596 583
764 468
908 877
169 626
845 854
630 48
541 574
836 678
174 969
208 952
950 107
7 474
814 540
407 132
335 353
846 390
269 251
291 248
377 345
793 739
91 684
609 91
620 192
285 738
773 175
165 60
672 607
306 217
302 729
266 871
35 674
325 50
700 362
710 167
821 166
621 273
66 763
658 91
133 316
594 737
436 35
971 526
632 73
429 359
957 368
180 256
909 192
645 898
762 674
548 615
83 43
149 218
418 88
154 264
147 509
585 553
478 76
569 269
384 955
346 407
748 393
692 754
160 573
904 819
181 425
274 478
832 565
363 276
358 968
483 64
589 59
449 867
261 853
946 652
220 806
372 25
380 630
13 356
321 332
813 227
67 35
530 73
812 41
272 706
623 541
14 80
395 696
862 625
258 789
92 479
965 227
136 847
404 714
369 390
722 203
300 98
668 533
740 568
545 585
528 779
232 418
518 374
105 571
200 837
636 614
820 556
75 168
953 353
721 226
271 53
809 682
472 635
141 956
419 913
482 647
295 646
313 89
400 701
32 624
642 26
649 956
347 785
277 661
340 394
435 837
868 897
911 367
463 102
716 796
718 322
715 281
65 659
46 951
364 191
19 165
330 869
648 497
588 176
112 380
861 876
239 292
30 209
334 420
361 91
808 786
881 65
159 419
643 919
373 460
323 574
935 542
732 84
129 788
598 538
539 838
465 891
143 718
162 473
337 249
932 136
508 167
413 932
549 574
781 376
677 146
834 43
708 714
99 378
778 312
850 137
802 835
532 952
10 470
122 82
440 296
123 254
666 141
771 615
784 873
970 622
790 634
457 386
560 52
452 78
234 181
47 902
42 504
503 612
366 410
490 52
917 450
550 883
637 185
575 620
520 621
515 373
308 295
889 456
760 271
462 773
536 682
765 655
759 349
115 533
307 97
57 31
145 818
491 691
604 926
454 518
229 303
336 250
702 371
593 916
735 341
959 599
403 893
843 537
135 950
886 564
331 341
62 967
801 931
855 619
857 312
173 97
3 760
695 523
375 545
963 361
653 322
447 715
600 102
923 784
933 723
197 382
58 689
517 358
427 193
184 55
199 218
113 120
79 28
772 207
758 172
314 498
222 171
590 922
480 232
223 834
887 965
426 76
915 841
848 252
103 707
627 61
512 580
189 63
225 168
389 297
469 809
501 865
49 779
791 180
357 379
724 499
431 383
90 854
23 546
562 312
301 918
516 147
826 644
489 635
914 503
894 862
111 754
704 554
406 6
219 329
584 552
18 365
233 307
651 433
39 865
782 793
713 636
-1
AC output: 392
Check input and AC output for thousands of problems on uDebug!

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 1218 - Perfect Service

Post by Farsan » Fri Oct 03, 2014 11:43 am

WA and the only testcase given by brianfry is too big to debug.

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>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_leading_zero_bits(int N){return __builtin_clz(N);}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}

//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const


using namespace std;

int dp[10002][2];
vector<int>g[10002],v[10002];
bool visited[10002];

int dfs(int no)
{
    visited[no]=true;
    int i,j,k;
    for(i=0,j=v[no].size();i<j;i++)
    {
        k=v[no][i];
        if(!visited[k])
        {
            g[no].push_back(k);
            //g[k].push_back(no);
            dfs(k);
        }
    }
}

int solve(int no,int place,int root)
{

    if(dp[no][place]!=-1)
    return dp[no][place];
    int i,j,k,m,n,a,b,c,d,mx;
    if(root)
    {
        if(place)
        {
            k=0;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,0,0);
                b=solve(m,1,0);
                c=min(a,b);
                k=k+c;
            }
            return dp[no][place]=1+k;
        }
        else
        {
            mx=inf;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,1,0);
                for(b=0,j=g[no].size();b<j&&a!=inf;b++)
                {
                    n=g[no][b];
                    if(m==n)
                    continue;
                    a=a+solve(n,0,0);
                }
                mx=min(mx,a);
            }
            return dp[no][place]=mx;
        }
    }
    else
    {
        if(place)
        {
            k=0;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,0,0);
                b=solve(m,1,0);
                c=min(a,b);
                k=k+c;
            }
            return dp[no][place]=1+k;
        }
        else
        {
            mx=inf;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,1,0);
                for(b=0,j=g[no].size();b<j&&a!=inf;b++)
                {
                    n=g[no][b];
                    if(n==m)
                    continue;
                    a=a+solve(n,0,0);
                }
                mx=min(mx,a);
            }
            if(j==0)
            mx=0;
            return dp[no][place]=mx;
        }
    }
}


int main()
{
    int i,j,k,m,n,a,b;
    while(inp1(n))
    {
        for(i=1;i<=n;i++)
        {
            v[i].clear();
            g[i].clear();
            dp[i][0]=-1;
            dp[i][1]=-1;
            visited[i]=false;
        }
        for(i=1;i<n;i++)
        {
            inp2(j,k);
            v[j].push_back(k);
            v[k].push_back(j);
        }
        for(i=1,j=0;i<=n;i++)
        {
            if(!visited[i])
            {
                dfs(i);
                a=solve(i,0,1);
                b=solve(i,1,1);
                j=j+min(a,b);
            }
        }
        cout<<j<<endl;
        inp1(k);
        if(k==-1)
        break;
    }
    return 0;
}


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

Re: 1218 - Perfect Service

Post by brianfry713 » Sat Oct 04, 2014 1:02 am

Input:

Code: Select all

3
1 2
3 1
0
1
0
5
3 4
2 4
5 4
1 4
0
7
1 5
4 1
3 5
2 3
6 5
7 2
0
10
7 1
3 7
5 1
2 7
6 1
8 5
9 5
4 6
10 6
0
8
1 6
3 6
2 6
4 2
5 1
8 3
7 8
0
5
5 1
2 1
4 5
3 4
0
3
2 3
1 3
0
8
4 7
3 4
2 4
1 2
8 3
5 7
6 2
0
9
6 1
2 6
4 2
9 2
3 2
5 6
7 2
8 3
0
1
0
10
2 3
5 2
8 3
7 3
9 7
4 7
10 9
1 3
6 4
0
1
0
7
1 3
6 3
4 3
7 6
2 1
5 7
0
8
7 3
4 7
2 4
8 3
6 2
5 8
1 2
0
5
5 4
1 5
2 1
3 1
0
8
3 6
7 6
2 6
4 2
8 7
1 7
5 2
0
2
2 1
0
10
8 9
1 8
4 9
6 9
7 6
5 1
10 1
3 7
2 4
0
9
2 5
1 5
9 1
4 2
8 1
7 1
6 4
3 8
0
9
1 3
9 1
4 3
5 9
8 4
2 5
7 1
6 4
0
9
1 6
7 1
8 7
2 6
5 7
9 5
4 9
3 2
0
7
4 6
2 6
5 2
7 5
1 6
3 5
0
5
1 4
3 4
5 3
2 1
0
10
10 3
7 3
9 10
6 10
8 7
1 3
2 3
5 1
4 3
0
10
8 3
6 3
7 6
2 3
5 8
9 2
4 3
10 7
1 7
0
7
3 7
6 3
5 3
2 5
4 3
1 4
0
10
10 7
2 10
4 10
6 4
9 10
8 6
1 7
3 4
5 3
0
4
2 1
4 1
3 1
0
1
0
1
0
5
1 3
2 3
4 1
5 4
0
1
0
1
0
5
4 3
2 4
5 2
1 5
0
9
4 6
8 6
9 4
2 4
7 8
5 8
3 4
1 3
0
1
0
10
3 8
7 8
4 8
2 7
6 2
5 6
10 2
1 8
9 8
0
4
1 3
4 1
2 1
0
8
6 5
3 6
8 3
7 6
2 3
1 5
4 8
0
8
7 8
4 7
2 7
3 8
5 7
6 4
1 4
0
2
2 1
0
7
4 6
2 6
1 2
7 1
3 7
5 7
0
7
2 7
5 2
1 5
6 2
3 1
4 2
0
4
3 4
2 4
1 3
0
2
1 2
0
10
3 8
6 3
5 3
4 8
10 4
1 10
9 1
2 9
7 9
0
4
4 3
2 4
1 2
0
2
1 2
0
8
4 2
6 4
8 6
5 4
7 5
1 5
3 5
0
10
9 2
7 2
8 7
4 7
1 8
5 9
10 7
6 7
3 4
0
10
2 6
8 6
3 6
7 6
10 7
1 7
5 10
9 3
4 7
0
7
3 1
7 3
2 7
6 7
5 6
4 2
0
7
6 4
7 4
5 6
3 6
2 6
1 6
0
7
7 3
1 7
4 7
2 4
6 3
5 3
0
3
3 2
1 3
0
6
2 1
6 1
4 2
3 4
5 2
0
2
1 2
0
3
3 1
2 3
0
5
1 3
4 1
5 3
2 3
0
1
0
3
2 1
3 1
0
3
1 3
2 3
0
7
6 5
7 5
4 7
1 5
2 1
3 4
0
4
3 2
1 3
4 1
0
8
2 3
5 2
7 2
4 3
8 4
1 8
6 3
0
2
1 2
0
9
7 3
5 3
4 7
8 4
9 7
6 3
2 9
1 8
0
2
1 2
0
1
0
1
0
1
0
8
1 5
6 5
3 6
8 6
2 6
4 8
7 8
0
10
6 5
10 5
9 5
2 6
4 2
8 5
1 8
3 10
7 8
0
4
1 3
4 1
2 3
0
6
4 1
6 1
2 4
5 2
3 5
0
8
8 7
6 8
3 8
2 3
4 7
5 8
1 7
0
2
2 1
0
3
1 3
2 1
0
2
1 2
0
6
1 3
5 1
6 5
4 3
2 6
0
4
2 3
4 2
1 4
0
5
3 2
4 2
5 2
1 3
0
4
3 4
2 4
1 3
0
10
8 2
5 2
1 2
10 2
6 8
4 10
7 10
9 10
3 2
0
8
2 1
3 2
6 3
4 2
7 1
8 1
5 4
0
9
4 9
5 4
7 9
2 7
8 7
6 5
3 8
1 7
0
8
2 3
4 3
7 3
1 2
5 7
6 5
8 6
0
2
1 2
0
5
5 2
1 5
3 5
4 1
0
9
9 8
5 8
6 8
1 8
7 9
3 9
2 9
4 3
0
1
0
6
5 3
4 5
6 5
2 3
1 2
0
6
5 6
2 6
1 5
4 1
3 2
0
8
3 6
4 3
8 6
5 6
7 8
1 6
2 5
0
2
2 1
0
10
4 3
1 4
7 1
6 7
5 3
8 3
10 1
2 6
9 10
0
4
4 2
1 2
3 2
0
8
4 7
6 7
3 6
2 6
5 6
8 2
1 2
0
5
3 5
4 3
1 4
2 3
-1
AC output:

Code: Select all

1
1
1
3
4
3
2
1
3
3
1
4
1
3
3
2
3
1
3
3
3
3
3
2
4
4
3
4
1
1
1
2
1
1
2
4
1
3
1
4
3
1
2
2
2
1
4
2
1
3
4
4
3
2
3
1
3
1
1
2
1
1
1
3
2
3
1
3
1
1
1
1
3
4
2
2
3
1
1
1
2
2
2
2
3
3
3
3
1
2
3
1
2
2
4
1
3
1
3
2
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 12 (1200-1299)”