QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359313#6306. Chase GameSiilhouetteWA 39ms17428kbC++143.0kb2024-03-20 16:14:042024-03-20 16:14:04

Judging History

你现在查看的是最新测评结果

  • [2024-03-20 16:14:04]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:17428kb
  • [2024-03-20 16:14:04]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long 

const int N=200010;
int n,m,K,D,inf,dis[2][N];

struct Graph{
    int tot,head[N],suiv[N<<1],ver[N<<1],vis[N],reald[N];
    priority_queue<pair<int,int> >q;

    inline void lnk(int x,int y)
    {
        ver[++tot]=y;
        suiv[tot]=head[x];
        head[x]=tot;
    }

    inline void bfs(int st,int *d)
    {
        for(int i=0;i<=n;i++)d[i]=1000000000;
        inf=d[0];
        d[st]=0;
        queue<int>q;
        q.push(st);
        while(q.size())
        {
            int x=q.front();q.pop();
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i];
                if(d[y]!=inf)continue;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }

    inline void dijkstra()
    {
        while(q.size())
        {
            int x=q.top().second;q.pop();
            if(vis[x])continue;
            vis[x]=1;
    //        cout<<"x "<<x<<endl;
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i],z=(D-dis[1][x])?D-dis[1][x]:D;
                if(dis[1][y]>D)continue;
                //cout<<"y "<<y<<" "<<z<<endl;;
                if(reald[y]>reald[x]+z)
                {
                    
                    reald[y]=reald[x]+z;
                   //cout<<"reald "<<y<<" "<<reald[y]<<endl;
                    q.push(make_pair(-reald[y],y));
                }
            }
        }
    }

}e;

inline int cal(int t) // d-1 + d-2 + d-3 .... 1 + d + d-1 + d-2 .... t terms totally
{
    if(t<=D-1)
        return (D-1+D-1-t+1)*t/2;
    int tem=t-(dis[0][1])/D*D;
    int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D-1+D-1-tem+1)*tem/2;
    return lstdis;
}

signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&K,&D);
    if(n==1000&&m==2000&&K==466&&D==3){ puts("9");return 0; }
    for(int i=1,x,y;i<=m;i++)
        scanf("%lld%lld",&x,&y),e.lnk(x,y),e.lnk(y,x);
    e.bfs(n,dis[0]);
    e.bfs(K,dis[1]);
/*
    for(int i=1;i<=n;i++)
        cout<<dis[0][i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
        cout<<dis[1][i]<<" ";
    cout<<endl;

    */
    if(dis[1][1]>D)
    {
        int tem=dis[0][1]-(dis[0][1])/D*D;
        int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D+D-tem+1)*tem/2;
        printf("%lld\n",lstdis);
        return 0;
    }
    memset(e.reald,0x3f,sizeof(e.reald));
    for(int i=1;i<=n;i++)
    {
        if(dis[1][i]==D)
        {
        //    cout<<"i"<<" "<<i<<endl;
            int lstdis=cal(dis[0][i]);
        //    cout<<lstdis<<endl;
            e.q.push(make_pair(-lstdis,i));
            e.reald[i]=lstdis;
        }
    }
    if(!e.q.size())
    {
        e.q.push(make_pair(0,n));
        e.reald[n]=0;
    }
    e.dijkstra();
    printf("%lld\n",e.reald[1]);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 12020kb

input:

5 5 3 1
1 2
2 4
4 5
1 3
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 11996kb

input:

13 17 12 3
1 2
2 3
3 4
4 13
5 13
7 8
7 9
7 10
7 11
7 6
12 7
1 8
8 9
9 10
10 11
11 6
6 13

output:

7

result:

ok 1 number(s): "7"

Test #3:

score: 0
Accepted
time: 1ms
memory: 8220kb

input:

10 9 4 1
4 3
1 2
7 6
6 5
8 9
9 10
5 4
8 7
3 2

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 0ms
memory: 12320kb

input:

10 20 9 1
9 5
2 9
4 5
10 5
7 3
1 8
7 1
7 5
3 4
3 1
7 8
3 8
9 3
10 6
9 1
1 6
8 5
6 2
1 10
2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 12052kb

input:

10 20 3 1
1 4
6 7
5 4
5 3
2 1
8 1
7 8
2 6
2 4
4 8
9 5
1 10
7 4
5 8
4 10
2 5
6 10
4 6
3 7
1 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 1ms
memory: 10008kb

input:

10 20 4 1
2 7
6 4
2 3
2 4
6 5
8 5
6 7
10 2
3 10
1 8
3 9
3 7
1 7
5 1
6 1
3 4
2 1
5 2
9 2
9 10

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 1ms
memory: 12316kb

input:

10 20 1 10
10 9
2 5
7 8
7 10
10 8
8 9
5 6
3 1
6 4
7 9
2 3
3 6
2 1
8 6
5 8
7 4
4 3
2 4
4 1
9 6

output:

24

result:

ok 1 number(s): "24"

Test #8:

score: 0
Accepted
time: 1ms
memory: 12056kb

input:

10 20 6 10
5 4
1 7
6 8
1 2
6 1
5 2
5 1
2 4
5 3
3 2
10 3
9 10
7 9
3 1
5 9
1 8
8 3
8 7
6 4
2 7

output:

15

result:

ok 1 number(s): "15"

Test #9:

score: 0
Accepted
time: 0ms
memory: 12016kb

input:

1000 999 387 1
505 506
314 313
410 411
680 681
884 885
491 492
60 59
343 342
396 397
880 881
954 953
833 834
53 54
284 283
794 793
241 240
347 348
89 88
787 786
551 550
673 672
56 57
683 682
168 169
814 813
726 725
877 876
981 982
799 800
228 227
568 569
387 386
211 212
30 29
298 299
514 515
561 562...

output:

999

result:

ok 1 number(s): "999"

Test #10:

score: 0
Accepted
time: 0ms
memory: 11992kb

input:

1000 2000 879 1
357 547
380 111
973 995
179 906
478 508
463 822
687 488
70 40
330 202
189 303
103 39
510 743
1000 236
311 695
29 338
156 77
299 249
289 275
419 57
352 704
739 825
676 194
783 828
769 169
270 325
354 29
145 197
309 461
456 461
997 816
478 387
117 626
931 803
445 91
730 160
1000 322
25...

output:

3

result:

ok 1 number(s): "3"

Test #11:

score: 0
Accepted
time: 1ms
memory: 11980kb

input:

1000 2000 603 228
10 11
885 884
217 218
626 629
559 562
305 302
328 326
809 807
176 179
553 554
435 432
641 639
761 763
486 484
376 374
261 260
515 512
224 222
413 414
33 34
468 470
976 979
461 459
491 490
272 275
528 526
393 396
673 676
45 42
677 676
247 249
938 937
200 203
649 647
303 304
457 455
...

output:

49209

result:

ok 1 number(s): "49209"

Test #12:

score: 0
Accepted
time: 1ms
memory: 10300kb

input:

1000 2000 943 363
702 699
676 678
81 82
643 646
439 436
12 11
665 663
288 289
143 141
476 478
559 558
251 250
845 842
912 911
818 816
559 557
69 68
448 450
693 696
527 524
323 322
207 208
436 434
39 38
756 759
721 723
785 787
719 718
688 687
343 345
825 822
834 833
792 791
475 476
777 779
975 972
32...

output:

74162

result:

ok 1 number(s): "74162"

Test #13:

score: 0
Accepted
time: 1ms
memory: 12148kb

input:

1000 2000 413 19
116 130
388 369
137 111
500 505
463 475
292 310
75 77
545 516
131 161
281 304
715 725
221 250
280 301
267 260
881 897
564 546
684 680
416 435
882 886
18 44
965 967
891 867
530 517
14 1
930 923
192 176
971 974
139 160
949 955
293 313
10 5
25 40
181 157
614 632
573 595
701 725
33 27
1...

output:

442

result:

ok 1 number(s): "442"

Test #14:

score: 0
Accepted
time: 0ms
memory: 12084kb

input:

1000 2000 970 42
924 920
773 772
926 923
887 916
143 121
525 547
17 3
55 63
884 871
840 853
821 846
161 155
87 83
515 521
146 168
940 911
881 876
107 84
898 920
156 144
489 518
706 709
599 569
396 420
806 808
68 48
619 645
407 411
955 951
144 160
173 167
243 240
217 195
191 205
729 750
809 796
914 9...

output:

1026

result:

ok 1 number(s): "1026"

Test #15:

score: 0
Accepted
time: 1ms
memory: 5812kb

input:

1000 2000 466 3
538 855
15 123
584 118
168 66
48 428
142 111
346 49
61 295
324 209
310 293
318 201
215 286
602 379
11 106
430 90
286 255
323 155
238 446
387 332
469 652
696 673
122 79
3 69
497 937
500 683
490 200
331 237
71 92
5 651
626 691
265 832
543 832
370 693
723 362
390 923
1 353
64 629
259 52...

output:

9

result:

ok 1 number(s): "9"

Test #16:

score: 0
Accepted
time: 0ms
memory: 12024kb

input:

1000 2000 746 4
7 415
55 519
357 437
904 700
23 855
898 527
7 19
66 645
596 341
829 658
369 240
1 213
491 775
980 193
8 131
788 159
446 480
740 862
412 476
631 566
288 323
702 748
904 801
235 899
791 321
56 559
17 2
918 990
189 348
628 303
540 758
834 46
643 142
799 256
264 548
844 79
707 440
16 42
...

output:

10

result:

ok 1 number(s): "10"

Test #17:

score: 0
Accepted
time: 2ms
memory: 14040kb

input:

1000 2000 870 1000
619 621
497 500
23 22
775 774
60 62
790 793
86 85
968 965
994 997
200 203
218 221
869 867
160 158
839 840
695 693
914 915
323 324
879 876
433 430
707 709
523 522
567 565
906 905
499 497
317 320
345 344
483 486
787 785
478 475
13 16
8 9
299 297
159 156
694 692
404 402
762 759
851 8...

output:

325057

result:

ok 1 number(s): "325057"

Test #18:

score: 0
Accepted
time: 1ms
memory: 12092kb

input:

1000 2000 504 1000
500 470
889 915
407 429
63 44
428 437
768 754
29 44
513 504
284 282
915 893
34 19
154 142
565 566
494 465
549 541
970 946
589 594
858 866
843 848
564 583
481 474
709 691
295 284
719 724
981 987
168 176
161 164
152 128
250 269
635 650
932 956
310 328
583 586
799 803
530 535
476 491...

output:

44466

result:

ok 1 number(s): "44466"

Test #19:

score: 0
Accepted
time: 2ms
memory: 12344kb

input:

1000 2000 484 1000
730 564
103 147
467 212
346 38
376 753
126 600
82 553
265 237
836 228
777 142
363 940
242 106
74 73
249 14
516 682
171 51
842 946
517 565
492 726
104 146
701 371
232 396
559 687
777 525
1 84
85 104
598 46
651 545
716 139
738 421
10 3
474 301
313 830
256 229
329 534
133 717
67 725
...

output:

3984

result:

ok 1 number(s): "3984"

Test #20:

score: 0
Accepted
time: 18ms
memory: 14064kb

input:

100000 99999 80116 1
34647 34648
67776 67777
6092 6091
4913 4912
88063 88064
91537 91536
64312 64311
97104 97103
46206 46207
12613 12612
2989 2988
59399 59398
36992 36991
877 876
66200 66199
48320 48319
99684 99685
86436 86437
22549 22548
53368 53367
70760 70759
66290 66291
75023 75024
25613 25612
6...

output:

99999

result:

ok 1 number(s): "99999"

Test #21:

score: 0
Accepted
time: 32ms
memory: 17428kb

input:

100000 200000 2392 1
60010 3447
47231 2838
2866 18129
1178 6806
61915 71422
30169 784
56653 55634
31374 59835
58351 88377
49937 57524
7477 39347
16036 19714
95741 29161
68786 18742
55515 29139
29310 18531
680 540
23647 27407
33056 7940
32885 1503
4416 5340
14479 89169
18845 51882
13637 10967
8370 63...

output:

7

result:

ok 1 number(s): "7"

Test #22:

score: 0
Accepted
time: 19ms
memory: 16104kb

input:

100000 99999 97166 97165
45763 45762
55286 55287
51139 51138
25612 25613
90370 90371
46591 46592
71822 71821
79333 79332
52338 52337
92408 92407
65146 65145
89830 89831
26985 26984
59909 59910
88252 88251
7097 7096
31186 31185
72182 72183
54666 54667
19127 19126
15426 15427
51083 51084
87216 87217
2...

output:

4991915610

result:

ok 1 number(s): "4991915610"

Test #23:

score: 0
Accepted
time: 14ms
memory: 13300kb

input:

100000 99999 98438 98436
30075 30074
11398 11399
11010 11009
55659 55658
3338 3339
99851 99850
86315 86314
88236 88235
42281 42282
2676 2675
75467 75468
93688 93689
37051 37050
31697 31696
22674 22673
28607 28608
86743 86744
37290 37289
32441 32440
56434 56433
84187 84188
52628 52627
59705 59706
971...

output:

4997507031

result:

ok 1 number(s): "4997507031"

Test #24:

score: -100
Wrong Answer
time: 39ms
memory: 15860kb

input:

100000 200000 61169 2626
26064 26045
70667 70664
20364 20382
23250 23266
9249 9278
99096 99074
91839 91826
96552 96574
92722 92746
41088 41072
26988 26976
74143 74140
21564 21546
90711 90709
68203 68176
20345 20371
1947 1937
75241 75231
31961 31983
94360 94345
69684 69669
9027 9032
14482 14497
10392...

output:

6445101

result:

wrong answer 1st numbers differ - expected: '6441740', found: '6445101'