QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693881 | #6306. Chase Game | ucup-team2179# | WA | 1ms | 3816kb | C++20 | 1.6kb | 2024-10-31 16:54:32 | 2024-10-31 16:54:34 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
int pre(int n){
return n * (n + 1) / 2;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n,m,k,d;
cin>>n>>m>>k>>d;
vector<int> a[n + 1]{};
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
a[u].pb(v);
a[v].pb(u);
}
auto bfs = [&](int u){
queue<int>q;
q.push(u);
vector<int> dis(n + 1, 1e18);
dis[u] = 0;
while(!q.empty()){
int u=q.front();
q.pop();
for(auto p:a[u]){
if(dis[p]==1e18){
dis[p] = dis[u] + 1;
q.push(p);
}
}
}
return dis;
};
auto disn=bfs(n);
auto disk=bfs(k);
set<pii>s;
vector<int> dis0(n + 1,1e18);
s.insert({0,1});
dis0[1] = 0;
while(!s.empty()){
auto [nowd,u]=*s.begin();
s.erase(s.begin());
for(auto p:a[u]){
if(disk[p]>=d)continue;
if(dis0[p]>nowd+d-disk[p]){
dis0[p] = nowd + d - disk[p];
s.insert({dis0[p], p});
}
}
}
int ans=1e18;
auto check = [&](int num)
{
return num / d * pre(d) + pre(d) - pre(d-num % d);
};
for (int i = 1;i<=n;i++){
ans = min(ans, dis0[i] + check(disn[i]));
// cout <<i<<" "<< dis0[i] <<" "<< check(disn[i]) << endl;
}
cout << ans << endl;
return 0;
}
詳細信息
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: 3560kb
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: 3816kb
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: 3596kb
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: 3612kb
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: 3592kb
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: 3816kb
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: 3564kb
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: 3700kb
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: 1ms
memory: 3676kb
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: -100
Wrong Answer
time: 1ms
memory: 3740kb
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:
37887
result:
wrong answer 1st numbers differ - expected: '49209', found: '37887'