QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#242179 | #3053. Marching Course | vlp | WA | 20ms | 10680kb | C++17 | 3.6kb | 2023-11-07 00:25:34 | 2023-11-07 00:25:35 |
Judging History
answer
#include <bits/stdc++.h>
#include <list>
#define len(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define ll long long
#define ull unsigned long long
#define ld long double
#define start time_t res1 = time(NULL)
#define finish \
time_t res2 = time(NULL); \
cerr << res2 - res1 << '\n'
const long long mod1 = 1e9 + 7;
const long long mod2 = 998244353;
const long long MAXLL = 9223372036854775807;
const long long MAXINT = 2147483647;
using namespace std;
void print(vector<pair<int, int>> a);
void print(vector<int> a);
void print(vector<vector<int>> a);
void print(vector<vector<char>> a);
void print(vector<char> a);
// #define mtask
#define int ll
int n, m, p;
vector<vector<vector<ld>>> g;
vector<vector<ld>> dist;
void solve(){
cin >> n >> m >> p;
g.resize(n);
dist.resize(n, vector<ld>(p + 1, -1e9));
dist[0][0] = 0;
for(int i = 0; i < m; ++i){
ld u, v, d, s;
cin >> u >> v >> d >> s;
--u, --v;
g[(int)u].push_back({v, d, s});
g[(int)v].push_back({u, d, s});
}
for(int i = 0; i < n; ++i){
ld mmax = 0;
for(auto x : g[i]) mmax = max(mmax, (ld)x[2] / (ld)x[1]);
g[i].push_back({(ld)i, 1, mmax});
}
vector<pair<int, int>> bfs(n, {1e9, 0});
bfs[0] = {0, 0};
set<pair<int, int>> q;
q.insert({0, 0});
while(len(q)){
auto [d, cur] = *q.begin();
q.erase(q.begin());
for(auto x : g[cur]){
if(bfs[x[0]].first > bfs[cur].first + x[1]){
bfs[x[0]].first = d + x[1];
bfs[x[0]].second = bfs[cur].second + x[2];
q.insert({bfs[x[0]].first, x[0]});
}
else if(bfs[x[0]].first == bfs[cur].first + x[1] && bfs[x[0]].second < bfs[cur].second + x[2]){
bfs[x[0]].first = d + x[1];
bfs[x[0]].second = bfs[cur].second + x[2];
q.insert({bfs[x[0]].first, x[0]});
}
}
}
ld mmax = 0;
//print(bfs);
for(int cur = 0; cur < n; ++cur){
for(auto x : g[cur]){
int ind = cur;
if(bfs[cur].first > bfs[x[0]].first){
ind = x[0];
}
else if(bfs[cur].first == bfs[x[0]].first && bfs[cur].second < bfs[x[0]].second) ind = x[0];
if(2 * bfs[ind].first > p) continue;
ld cur = (p - 2 * bfs[ind].first) * x[2] / x[1];
mmax = max(mmax, cur + 2 * bfs[ind].second);
}
}
cout << mmax << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(40);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
#ifdef mtask
int t;
cin >> t;
while (t--)
#endif
solve();
}
void print(vector<pair<int, int>> a) {
for (int i = 0; i < len(a); ++i) {
cout << a[i].first << ' ' << a[i].second << '\n';
}
}
void print(vector<int> a) {
for (int i = 0; i < len(a); ++i) {
cout << a[i] << ' ';
}
cout << '\n';
}
void print(vector<vector<int>> a) {
for (int i = 0; i < len(a); ++i) {
print(a[i]);
}
}
void print(vector<char> a) {
for (int i = 0; i < len(a); ++i) {
cout << a[i];
}
cout << '\n';
}
#ifndef int
void print(vector<ll> a) {
for (int i = 0; i < len(a); ++i) {
cout << a[i] << ' ';
}
cout << '\n';
}
#endif
void print(vector<vector<char> > a) {
for (int i = 0; i < len(a); ++i) {
print(a[i]);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3924kb
input:
3 3 4 1 2 1 1 2 3 2 4 3 1 1 1
output:
6
result:
ok - 1 values
Test #2:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
4 3 9 1 2 2 1 1 3 2 2 1 4 2 3
output:
13.5
result:
ok - 1 values
Test #3:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
4 3 5 1 2 10 1 2 3 2 100 1 4 3 10
output:
16.66666666666666666608842550800773096853
result:
ok - 1 values
Test #4:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
3 3 10 1 2 3 1 1 3 4 5 2 3 2 10
output:
22
result:
ok - 1 values
Test #5:
score: 0
Accepted
time: 0ms
memory: 4732kb
input:
65 2080 409 30 37 338 348 10 15 132 14 7 32 215 699 17 62 36 468 5 43 294 92 7 22 426 281 24 48 180 532 54 59 289 784 8 65 12 48 14 63 368 647 29 36 32 46 16 35 233 396 2 54 2 336 22 36 431 890 35 48 367 897 35 45 326 995 9 35 398 464 28 57 442 976 22 47 437 893 3 7 273 711 37 60 217 765 33 49 424 7...
output:
330695
result:
ok - 1 values
Test #6:
score: 0
Accepted
time: 12ms
memory: 9044kb
input:
183 16653 688 87 158 526 44 135 148 214 291 85 138 454 863 86 142 582 489 125 147 702 90 47 127 67 766 96 153 553 255 53 68 441 14 167 175 455 341 29 123 43 771 82 152 49 645 74 100 697 226 154 157 256 454 78 146 467 17 33 119 101 419 100 168 409 300 58 171 515 256 48 166 475 973 49 83 102 885 36 52...
output:
653768
result:
ok - 1 values
Test #7:
score: 0
Accepted
time: 7ms
memory: 5968kb
input:
124 7626 363 19 60 28 989 79 117 14 671 68 84 242 953 98 112 161 310 6 99 168 431 12 69 287 286 19 57 330 955 39 54 258 243 64 94 260 179 9 61 125 254 16 19 211 422 20 108 22 903 14 77 97 584 75 111 358 37 63 102 341 53 16 29 104 232 35 94 331 846 105 106 158 682 41 54 42 328 75 109 352 422 5 103 19...
output:
329925
result:
ok - 1 values
Test #8:
score: 0
Accepted
time: 15ms
memory: 8804kb
input:
176 15400 718 8 166 138 728 19 62 687 839 40 120 703 359 58 102 138 867 19 171 601 623 107 156 638 396 92 171 65 156 132 144 613 858 150 175 19 515 13 158 479 562 72 170 63 520 55 73 63 865 4 131 8 393 91 146 408 604 128 137 616 234 28 172 409 42 111 173 684 522 39 166 494 644 63 141 68 8 82 117 251...
output:
651238
result:
ok - 1 values
Test #9:
score: 0
Accepted
time: 0ms
memory: 4984kb
input:
69 2346 775 8 47 41 822 61 67 24 865 4 51 683 8 44 58 391 232 18 61 518 125 17 29 123 746 38 58 103 557 39 59 734 484 38 45 68 699 14 24 316 33 3 43 542 903 13 61 786 319 11 35 132 303 7 33 666 748 16 69 252 373 3 37 539 172 14 41 643 461 15 45 540 271 3 31 175 417 47 60 500 836 52 58 609 524 49 69 ...
output:
374325
result:
ok - 1 values
Test #10:
score: 0
Accepted
time: 16ms
memory: 9928kb
input:
200 19900 710 40 61 574 538 90 181 354 374 1 148 536 286 79 159 238 203 119 156 1 52 88 190 232 89 146 193 274 71 133 167 324 413 4 96 733 328 26 159 654 372 184 192 486 674 75 189 243 751 137 147 733 11 68 71 102 239 38 111 262 146 91 162 353 6 26 120 563 193 82 159 270 66 32 106 730 634 46 180 611...
output:
656650
result:
ok - 1 values
Test #11:
score: 0
Accepted
time: 15ms
memory: 8548kb
input:
200 19900 282 9 165 10 656 82 88 293 921 84 95 250 407 2 61 86 884 53 182 57 978 31 191 65 26 17 29 4 571 14 143 176 126 67 193 29 927 83 184 14 20 103 121 125 926 94 128 128 671 94 104 226 90 47 119 31 750 101 166 289 889 24 102 146 662 68 121 29 234 32 168 136 118 48 175 62 288 85 157 127 693 72 1...
output:
262038
result:
ok - 1 values
Test #12:
score: 0
Accepted
time: 20ms
memory: 10680kb
input:
200 19900 985 52 92 473 209 74 175 858 879 70 183 234 750 57 137 266 314 33 67 115 190 86 191 186 243 86 160 351 772 25 96 891 974 142 192 116 938 23 184 531 758 106 199 629 809 154 185 775 971 6 129 759 79 115 157 147 98 28 165 932 593 9 156 957 503 10 152 722 370 73 131 117 132 78 177 192 410 72 1...
output:
850080
result:
ok - 1 values
Test #13:
score: 0
Accepted
time: 19ms
memory: 8520kb
input:
200 19900 252 31 107 214 15 103 107 169 488 47 176 238 714 8 35 139 71 49 75 125 334 12 41 141 675 102 162 130 775 62 88 152 769 124 198 237 686 29 80 51 113 28 91 156 183 78 124 1 785 19 181 4 919 59 113 85 818 80 137 202 72 45 144 107 179 46 80 36 961 18 19 201 13 14 134 218 452 36 108 83 807 42 1...
output:
232920
result:
ok - 1 values
Test #14:
score: 0
Accepted
time: 19ms
memory: 8432kb
input:
200 19900 231 93 117 160 925 178 188 1 87 11 110 238 725 14 75 173 225 73 194 24 710 12 137 186 475 99 182 5 595 24 93 8 55 29 176 116 982 156 182 245 844 56 176 150 49 72 86 93 978 168 172 39 133 15 80 66 357 190 193 75 924 109 187 24 853 21 185 240 976 14 65 145 162 58 125 230 75 79 177 189 310 73...
output:
219056
result:
ok - 1 values
Test #15:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
24 134 820 14 19 193 915 16 18 333 685 4 12 180 21 7 15 250 503 7 23 414 992 7 20 755 750 8 18 791 427 6 7 882 630 3 24 851 663 15 16 639 831 11 21 200 792 6 14 270 606 10 15 7 323 7 10 426 385 3 6 711 481 4 18 189 735 1 6 483 420 15 17 522 855 6 13 814 173 2 10 738 177 1 12 470 175 9 18 178 611 1 8...
output:
14451.142857142857143237790751300053671
result:
ok - 1 values
Test #16:
score: 0
Accepted
time: 3ms
memory: 6500kb
input:
173 7521 340 59 149 129 898 12 91 208 987 6 32 334 460 138 173 279 514 64 150 307 150 84 134 168 231 88 153 325 713 73 131 139 504 17 53 259 579 136 148 158 415 60 138 5 138 36 154 102 631 3 109 228 372 42 73 131 229 108 151 164 978 18 49 295 753 67 123 193 756 27 75 198 975 7 171 99 70 9 10 121 445...
output:
251072
result:
ok - 1 values
Test #17:
score: 0
Accepted
time: 0ms
memory: 4752kb
input:
68 1125 423 6 57 432 813 6 21 188 184 30 37 305 159 13 22 205 949 7 51 22 192 7 47 166 717 24 32 197 934 11 65 333 27 41 46 235 196 23 32 56 936 37 49 166 628 45 50 69 43 52 67 324 561 9 13 460 601 51 66 120 845 9 66 211 66 53 66 48 210 40 62 280 194 42 51 123 358 30 45 91 922 2 13 247 419 32 50 128...
output:
278564
result:
ok - 1 values
Test #18:
score: -100
Wrong Answer
time: 0ms
memory: 6520kb
input:
134 4471 834 1 127 20 325 37 50 658 472 14 54 55 506 48 94 215 572 21 123 95 104 74 91 670 685 20 34 81 261 30 77 309 283 57 90 571 380 2 66 787 503 46 71 427 397 63 127 150 82 11 131 337 425 40 78 834 210 67 103 492 787 9 95 91 202 59 112 770 229 86 119 636 706 43 132 55 907 28 88 687 327 73 88 471...
output:
676510
result:
wrong answer - (1st value) expected: 678182.0000000000000000, actual: 676510.0000000000000000