QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #593615 | #5054. City Brain | DaiRuiChen007 | WA | 72ms | 10616kb | C++17 | 1.6kb | 2024-09-27 15:02:00 | 2024-09-27 15:02:00 |
Judging History
answer
#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
const int MAXN=5005;
const ll inf=2e18;
int n,m,k;
vector <int> G[MAXN];
struct graph {
int s,t,d[MAXN];
bool vis[MAXN];
bitset <MAXN> f[MAXN];
vector <int> ord;
int bfs() {
queue <int> q;
memset(d,0x3f,sizeof(d));
q.push(s),d[s]=0;
while(q.size()) {
int u=q.front(); q.pop();
ord.push_back(u),f[u][u]=1;
for(int v:G[u]) {
if(d[v]>d[u]+1) {
d[v]=d[u]+1,q.push(v),f[v]=f[u];
} else if(d[v]==d[u]+1) f[v]|=f[u];
}
}
return d[t];
}
} X,Y;
ll q1(ll x) {
ll z=sqrt(x)+10;
while(z*(z-1)>x) --z;
return z;
}
ll q2(ll x) {
ll z=sqrt(2*x)+10;
while(z*(z-1)/2>x) --z;
return z;
}
signed main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
scanf("%d%d%d%d",&X.s,&X.t,&Y.s,&Y.t);
int z=0,x=X.bfs(),y=Y.bfs();
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
bool fx=X.f[i][X.s]&&X.f[j][i]&&X.f[X.t][j];
bool fy=Y.f[i][Y.s]&&Y.f[j][i]&&Y.f[Y.t][j];
fy|=Y.f[j][Y.s]&&Y.f[i][j]&&Y.f[Y.t][i];
if(fx&&fy) z=max(z,X.d[j]-X.d[i]);
}
if(!x&&!y&&!z) return puts("0"),0;
ll l=1,r=inf,p=0;
while(l<=r) {
ll mid=(l+r)>>1;
if((q2(mid)-1)*z+(q1(mid)-1)*(x+y-2*z)<=k) l=mid+1,p=mid;
else r=mid-1;
}
ll s1=q1(p),s2=q2(p),q=k-(s2-1)*z-(s1-1)*(x+y-2*z);
cerr<<x<<" "<<y<<" "<<z<<" "<<s1<<" "<<s2<<" "<<p<<" "<<q<<"\n";
if((s2+1)*s2/2<(s1+1)*s1) {
printf("%.16Lf",(ld)(x+y-2*z)/s1+((ld)(z-q)/s2+(ld)q/(s2+1))*2);
} else {
printf("%.16Lf",(ld)q/(s1+1)+(ld)(x+y-2*z-q)/s1+(ld)z/s2*2);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 10236kb
input:
6 5 1 1 2 3 2 2 4 4 5 4 6 1 5 3 6
output:
5.0000000000000000
result:
ok found '5.000000000', expected '5.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 10080kb
input:
1 0 100 1 1 1 1
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 10204kb
input:
4 2 3 1 2 3 4 1 2 3 4
output:
0.8333333333333333
result:
ok found '0.833333333', expected '0.833333333', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 10360kb
input:
6 5 1 1 2 3 2 2 4 4 5 4 6 1 5 6 3
output:
5.0000000000000000
result:
ok found '5.000000000', expected '5.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 70ms
memory: 10376kb
input:
5000 4999 1000000000 1 2 1 3 1 4 1 5 6 2 7 3 8 4 9 5 10 6 11 7 12 8 13 9 14 10 15 11 16 12 17 13 18 14 19 15 20 16 21 17 22 18 23 19 24 20 25 21 26 22 27 23 28 24 29 25 30 26 31 27 32 28 33 29 34 30 35 31 36 32 37 33 38 34 39 35 40 36 41 37 42 38 43 39 44 40 45 41 46 42 47 43 48 44 49 45 50 46 51 47...
output:
0.0249898760756145
result:
ok found '0.024989876', expected '0.024989876', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 10220kb
input:
10 9 305097549 2 1 8 9 6 7 5 4 8 7 4 3 2 3 9 10 6 5 4 3 2 1
output:
0.0000000131105608
result:
ok found '0.000000013', expected '0.000000013', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 10240kb
input:
10 9 9 4 2 3 6 8 6 2 1 7 9 5 2 2 3 10 9 7 4 8 7 9 5
output:
3.8333333333333333
result:
ok found '3.833333333', expected '3.833333333', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 10368kb
input:
10 9 19 5 2 4 1 2 1 6 5 10 8 8 1 9 3 7 6 1 3 7 7 6 4
output:
0.7000000000000000
result:
ok found '0.700000000', expected '0.700000000', error '0.000000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 10364kb
input:
100 99 149 82 77 11 14 99 94 29 24 41 31 52 57 64 73 42 32 85 84 88 86 54 59 75 66 38 28 92 90 9 19 60 61 24 19 24 31 21 18 38 47 67 74 79 89 64 66 34 29 23 16 87 83 11 16 2 4 10 11 76 77 36 32 18 22 71 72 79 77 97 96 47 48 43 34 63 55 51 45 91 94 3 1 31 39 41 44 51 58 6 10 48 54 74 76 7 15 18 13 32...
output:
1.8059829059829060
result:
ok found '1.805982906', expected '1.805982906', error '0.000000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 10212kb
input:
100 99 126 23 98 27 75 2 7 81 83 10 13 99 3 10 7 70 56 28 16 3 15 18 16 51 55 1 33 6 3 53 61 3 1 68 76 68 85 26 79 40 86 28 37 25 16 12 14 23 48 22 3 66 96 16 39 41 90 69 100 97 89 37 84 51 37 32 25 36 14 35 21 67 20 7 27 23 31 4 23 32 34 44 1 66 23 95 70 42 73 26 7 19 38 93 58 39 88 2 65 1 12 81 2 ...
output:
0.2727272727272727
result:
ok found '0.272727273', expected '0.272727273', error '0.000000000'
Test #11:
score: 0
Accepted
time: 72ms
memory: 10384kb
input:
5000 4999 7363 4100 4099 2570 2569 494 493 608 609 3424 3423 1771 1770 4935 4934 1536 1537 2704 2703 2429 2428 4048 4049 2708 2709 3982 3981 1866 1867 1779 1780 1491 1490 3719 3720 3960 3959 1515 1516 2157 2158 3798 3799 4624 4625 2626 2627 4882 4883 2769 2770 4999 4998 514 513 3236 3237 3424 3425 2...
output:
365.9000000000000000
result:
ok found '365.900000000', expected '365.900000000', error '0.000000000'
Test #12:
score: 0
Accepted
time: 55ms
memory: 10472kb
input:
5000 4999 1713 4590 4518 4868 4954 2977 2986 2091 2190 458 540 1668 1738 2670 2760 371 441 4778 4800 4282 4347 534 557 1560 1498 2444 2430 4602 4520 1361 1457 4934 4918 963 984 2305 2274 798 842 4150 4174 1102 1038 1264 1234 115 175 4994 4901 3375 3459 530 468 1517 1480 1080 1150 4637 4568 2456 2414...
output:
6.6261189258312020
result:
ok found '6.626118926', expected '6.626118926', error '0.000000000'
Test #13:
score: 0
Accepted
time: 56ms
memory: 10616kb
input:
5000 4999 603835068 223 714 1868 220 1010 1047 1227 21 745 933 1281 1894 891 1005 4601 158 880 44 894 310 1418 4453 819 2380 4555 2795 632 4515 321 2239 100 1280 258 1374 827 616 4922 3842 3482 4721 1764 2675 1133 225 3144 124 3169 683 920 2958 370 534 72 255 648 3923 3013 852 977 284 2880 3728 53 4...
output:
0.0000014904731490
result:
ok found '0.000001490', expected '0.000001490', error '0.000000000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 10180kb
input:
10 10 629318717 4 9 2 10 8 7 7 6 3 2 9 10 4 9 8 10 3 4 1 6 8 4 4 7
output:
0.0000000436746603
result:
ok found '0.000000044', expected '0.000000044', error '0.000000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 10360kb
input:
10 20 857 1 9 5 8 3 9 8 9 4 2 9 5 2 3 7 6 5 10 4 1 9 3 7 4 1 3 5 6 3 1 7 9 6 3 8 6 5 4 8 7 2 2 1 6
output:
0.0046565837263512
result:
ok found '0.004656584', expected '0.004656584', error '0.000000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 10428kb
input:
10 100 884099588 8 6 3 8 3 6 8 3 2 6 7 4 2 1 7 4 5 1 7 3 9 10 3 1 10 5 5 6 5 1 9 10 4 1 10 4 8 10 6 3 10 7 7 3 9 10 7 10 2 10 3 2 3 10 8 3 10 5 5 10 9 4 2 9 3 7 2 5 10 2 9 10 8 5 10 7 6 7 4 7 1 3 7 9 10 6 1 8 6 3 1 4 1 9 2 7 5 3 7 4 6 2 1 4 6 10 6 7 10 1 8 10 4 9 7 8 10 4 9 3 3 8 4 10 6 9 10 8 5 9 5...
output:
0.0000000045243772
result:
ok found '0.000000005', expected '0.000000005', error '0.000000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 10428kb
input:
100 100 730 42 80 21 28 34 48 2 21 38 48 23 61 66 5 5 86 69 6 69 82 9 63 69 50 63 54 62 8 21 42 16 97 41 86 24 51 44 95 11 97 10 32 89 8 40 19 26 12 23 46 28 89 82 43 72 96 24 25 41 53 56 53 80 70 42 44 27 32 60 50 61 100 73 36 90 53 97 59 5 79 56 78 78 95 39 80 74 20 63 46 45 7 80 91 37 5 21 49 65 ...
output:
0.0340136054421769
result:
ok found '0.034013605', expected '0.034013605', error '0.000000000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 10236kb
input:
100 400 586010750 64 4 23 78 94 87 20 84 89 21 75 94 53 26 50 42 83 88 59 19 73 10 33 65 78 99 58 52 59 77 40 46 83 40 28 61 59 91 3 93 33 75 4 22 74 38 31 17 69 43 64 4 6 80 53 40 86 27 98 81 37 97 65 86 4 89 62 24 34 60 9 42 28 42 56 36 13 41 59 55 19 78 28 35 49 71 35 96 97 92 86 75 72 89 84 58 5...
output:
0.0000000702071339
result:
ok found '0.000000070', expected '0.000000070', error '0.000000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 10288kb
input:
100 5000 464 19 53 55 77 19 27 37 30 65 99 68 27 61 7 95 27 43 10 86 43 14 84 9 79 17 40 26 28 52 55 26 100 86 15 45 85 32 65 85 79 71 23 9 26 64 96 74 45 4 7 61 50 62 65 92 14 74 100 8 66 67 40 63 47 8 12 100 48 79 99 100 13 4 43 65 7 46 71 10 27 77 31 76 90 97 34 52 34 98 66 17 56 67 70 25 32 13 4...
output:
0.0192721257237386
result:
ok found '0.019272126', expected '0.019272126', error '0.000000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 10512kb
input:
100 5000 814 36 69 5 55 40 38 83 75 93 23 53 14 97 86 11 22 4 83 32 93 64 17 30 51 63 69 35 49 78 42 53 2 62 53 36 20 72 85 38 54 16 1 22 8 39 85 36 38 12 56 94 59 96 91 79 38 73 68 25 36 31 86 36 55 100 98 18 48 2 38 90 70 81 64 46 52 2 62 16 6 30 91 13 51 29 94 75 13 39 25 26 69 46 76 85 14 12 70 ...
output:
0.0110159448394743
result:
ok found '0.011015945', expected '0.011015945', error '0.000000000'
Test #21:
score: 0
Accepted
time: 4ms
memory: 10532kb
input:
1000 5000 989 560 586 752 743 511 370 809 214 823 456 13 240 413 613 592 354 935 810 738 313 347 635 924 904 583 44 119 236 114 986 639 738 95 550 878 578 617 846 902 111 215 995 381 71 810 174 769 860 747 212 643 538 325 906 785 780 268 955 500 648 296 156 859 204 289 538 544 551 51 915 610 377 306...
output:
0.0491972815916478
result:
ok found '0.049197282', expected '0.049197282', error '0.000000000'
Test #22:
score: 0
Accepted
time: 13ms
memory: 10296kb
input:
2500 5000 88677634 382 19 1966 1714 2238 1504 1385 1158 1060 437 354 581 1337 115 1113 1915 491 759 869 525 590 456 2039 1023 2365 1231 1910 994 17 6 673 985 243 732 1585 340 2373 1179 1666 142 277 1198 689 1805 980 1177 35 1538 12 1843 172 1644 1312 798 268 1659 275 825 1597 1773 971 1605 442 303 1...
output:
0.0000013644927084
result:
ok found '0.000001364', expected '0.000001364', error '0.000000000'
Test #23:
score: 0
Accepted
time: 60ms
memory: 10528kb
input:
5000 5000 269 4233 1430 2141 374 3248 2625 805 812 2960 620 3654 2471 1728 3454 2410 4766 152 600 3065 935 411 2248 2085 2562 4504 3462 2748 3253 4982 4173 2870 4624 3335 3912 2425 3259 2554 4250 4800 729 1254 83 2875 4660 1771 538 2225 4070 567 2146 4091 2145 4783 4304 4913 1080 225 2053 308 3837 4...
output:
0.5995670995670996
result:
ok found '0.599567100', expected '0.599567100', error '0.000000000'
Test #24:
score: 0
Accepted
time: 16ms
memory: 10472kb
input:
2500 4900 66276062 2402 2403 1914 1964 1668 1667 849 848 2083 2033 1518 1468 268 218 1042 1043 935 934 1273 1323 1126 1127 1034 1035 765 766 1593 1592 1322 1372 823 773 7 57 912 962 413 463 1612 1562 2442 2492 754 704 430 431 2183 2233 1633 1632 268 267 1209 1159 2075 2076 1212 1211 956 1006 676 726...
output:
0.0000543182052806
result:
ok found '0.000054318', expected '0.000054318', error '0.000000000'
Test #25:
score: 0
Accepted
time: 16ms
memory: 10480kb
input:
2500 4400 228604105 2237 2236 2451 2452 2311 2261 1615 1665 738 739 1928 1978 1989 1990 1369 1370 515 514 1254 1255 2039 2089 485 435 239 289 951 1001 1387 1388 899 898 330 380 1619 1669 901 951 805 855 2054 2104 2273 2272 1220 1221 635 636 606 556 383 382 264 265 2186 2185 733 734 1082 1081 1164 11...
output:
0.0000093421760650
result:
ok found '0.000009342', expected '0.000009342', error '0.000000000'
Test #26:
score: 0
Accepted
time: 16ms
memory: 10480kb
input:
2500 3900 286884850 2043 1993 2096 2146 292 242 1731 1681 697 647 1359 1309 2047 1997 71 121 1949 1999 1540 1539 2333 2383 350 400 1000 999 1362 1412 1415 1414 1775 1774 147 97 921 971 1311 1310 781 831 67 68 281 280 351 352 1312 1311 853 803 586 636 967 966 1268 1269 505 555 713 763 2491 2490 1547 ...
output:
0.0000027328035045
result:
ok found '0.000002733', expected '0.000002733', error '0.000000000'
Test #27:
score: -100
Wrong Answer
time: 12ms
memory: 10300kb
input:
2500 3500 585176204 1084 1083 436 386 965 966 1150 1100 2302 2303 1836 1786 717 718 164 165 1336 1335 2362 2361 2283 2333 226 276 1099 1149 2012 2011 697 647 190 191 213 163 1402 1403 300 299 2311 2312 260 259 200 199 1065 1064 2307 2257 424 474 1423 1424 2444 2394 218 168 423 373 1229 1228 1242 124...
output:
0.0000069247427286
result:
wrong answer 1st numbers differ - expected: '0.0000067', found: '0.0000069', error = '0.0000002'