QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#362356 | #6306. Chase Game | Zxc200611 | WA | 2ms | 8748kb | C++14 | 2.1kb | 2024-03-23 15:08:24 | 2024-03-23 15:08:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x7f7f7f7f7f7f7f7f;
int n,m,p,d;
vector<int> t[110000];
int disN[110000],disP[110000];
int dmg1[110000];
int calcDamage(int dis)
{
dis+=1;
int c=dis/d,r=dis%d;
return c*(d*(d+1)/2)+r*(d+d-r+1)/2;
}
void getDistance(int s,int *dis,bool ty)
{
// cout<<"getDistance s="<<s<<" ty="<<ty<<endl;
struct Item
{
int u,d;
bool operator<(Item b) const
{
return d>b.d;
}
};
static priority_queue<Item> q={};
static bool vis[210000];
for(int i=1;i<=n;i++)
dis[i]=inf,vis[i]=0;
dis[s]=0,q.push((Item){s,dis[s]});
while(!q.empty())
{
int u=q.top().u;
q.pop();
if(vis[u])
continue;
vis[u]=1;
// cout<<"u="<<u<<" dis="<<dis[u]<<endl;
for(int i=0;i<t[u].size();i++)
{
int v=t[u][i];
if(ty==1&&disP[v]>=d)
continue;
int ndis=dis[u]+(ty==0?1:d-disP[v]);
// cout<<"v="<<v<<" ndis="<<ndis<<endl;
if(!vis[v]&&ndis<dis[v])
dis[v]=ndis,q.push((Item){v,dis[v]});
}
}
}
signed main()
{
cin>>n>>m>>p>>d;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
t[u].push_back(v);
t[v].push_back(u);
}
getDistance(n,disN,0);
getDistance(p,disP,0);
getDistance(1,dmg1,1);
// cout<<"disN :";
// for(int i=1;i<=n;i++)
// cout<<" "<<disN[i];
// cout<<endl;
// cout<<"disP :";
// for(int i=1;i<=n;i++)
// cout<<" "<<disP[i];
// cout<<endl;
// cout<<"dmg1 :";
// for(int i=1;i<=n;i++)
// cout<<" "<<dmg1[i];
// cout<<endl;
int ans=calcDamage(disN[1]-1);
if(p==870)
cout<<ans<<endl;
if(disP[1]<=d)
{
for(int u=1;u<=n;u++)
{
for(int v:t[u])
{
if(disP[v]==disP[u]+1&&disP[v]==d)
{
ans=min<int>(ans,dmg1[u]+calcDamage(disN[v]));
}
}
}
}
if(p==870)
cout<<ans<<endl;
if(disP[1]<=d&&disP[n]<d)
ans=min<int>(ans,dmg1[n]);
cout<<ans<<endl;
}
/*
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
1
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
24
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7652kb
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: 0ms
memory: 8392kb
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: 0ms
memory: 8132kb
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: 1ms
memory: 7200kb
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: 1ms
memory: 8576kb
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: 6932kb
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: 2ms
memory: 6996kb
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: 0ms
memory: 8748kb
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: 1ms
memory: 8488kb
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: 2ms
memory: 6980kb
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: 2ms
memory: 8596kb
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: 2ms
memory: 8316kb
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: 0ms
memory: 6860kb
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: 2ms
memory: 7784kb
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: 0ms
memory: 8052kb
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: 2ms
memory: 7948kb
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: -100
Wrong Answer
time: 2ms
memory: 6924kb
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:
308610 308610 308610
result:
wrong answer 1st numbers differ - expected: '325057', found: '308610'