QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#296405 | #6306. Chase Game | HJR | WA | 7ms | 5372kb | C++23 | 2.8kb | 2024-01-02 22:54:02 | 2024-01-02 22:54:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
#define int long long
struct node
{
int u,w,ck;
bool operator<(const node&t)const{
return w>t.w;
}
};
void solve(){
int n,m,k,d;
cin>>n>>m>>k>>d;
vector<vector<int>> adj(n+1);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
map<pair<int,int>,int> mp;
// vector<int> kd(n+1);
queue<int> q;
vector<bool> vis(n+1);
q.push(k);
int cd=0;
while(!q.empty()){
int cn=q.size();
for(int i=0;i<cn;i++){
int cu=q.front();
q.pop();
if(vis[cu])
continue;
vis[cu]=1;
mp[{k,cu}]=mp[{cu,k}]=cd;
// kd[cu]=cd;
for(auto x:adj[cu]){
q.push(x);
}
}
cd++;
}
for(int i=1;i<=n;i++)
mp[{i,i}]=0;
vector<int> res(n+1,1e18);
auto dij=[&](){
priority_queue<node> q;
q.push({1,0,k});
res[1]=0;
while(!q.empty()){
node cur=q.top();
q.pop();
for(auto x:adj[cur.u]){
int dis=mp[{x,cur.ck}];
// debug(x);
// debug(cur.ck);
// debug(dis);
if(d-dis<=0){
if(res[cur.u]+d<res[x]){
res[x]=res[cur.u]+d;
q.push({x,res[cur.u]+d,x});
}
for(auto xx:adj[x]){
mp[{xx,x}]=mp[{x,xx}]=1;
}
}
else{
if(res[cur.u]+d-dis<res[x]){
res[x]=res[cur.u]+d-dis;
q.push({x,res[cur.u]+d-dis,cur.ck});
}
for(auto xx:adj[x]){
if(mp.count({xx,cur.ck})){
mp[{xx,cur.ck}]=mp[{cur.ck,xx}]=min(mp[{xx,cur.ck}],dis+1);
}
else
mp[{xx,cur.ck}]=mp[{cur.ck,xx}]=dis+1;
// if(mp[{xx,cur.ck}]==3){
// debug(xx);
// debug(cur.ck);
// }
}
}
}
}
};
dij();
// int adasd=mp[{13,8}];
// debug(adasd);
cout<<res[n]<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t=1;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 3664kb
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: 3568kb
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: 3624kb
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: 3620kb
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: 0ms
memory: 3620kb
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: 0ms
memory: 3612kb
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: 3580kb
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: 2ms
memory: 4032kb
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: 5ms
memory: 4164kb
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: 3ms
memory: 4128kb
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: 4ms
memory: 4000kb
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: 4ms
memory: 4052kb
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: 5ms
memory: 4356kb
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: -100
Wrong Answer
time: 7ms
memory: 5372kb
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:
7
result:
wrong answer 1st numbers differ - expected: '9', found: '7'