QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#374711#3053. Marching CourseSolitaryDream#WA 7ms13356kbC++171.6kb2024-04-02 17:24:052024-04-02 17:24:06

Judging History

你现在查看的是最新测评结果

  • [2024-04-02 17:24:06]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:13356kb
  • [2024-04-02 17:24:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+1e3+7;

struct ND {
    int s;
    int d;
};

ND operator +(const ND &a,const ND &b)
{
    return {a.s+b.s,a.d+b.d};
}

bool operator <(const ND &a,const ND &b)
{
    if(a.d!=b.d)
        return a.d>b.d;
    return a.s<b.s;
}

int n,m;

vector<pair<int,ND> >g[N];

ND d[N];

int use[N];

priority_queue<pair<ND,int> > q;

int p;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>p;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        int d,p;
        cin>>u>>v>>d>>p;
        g[u].push_back({v,{p,d}});
        g[v].push_back({u,{p,d}});
    }
    for(int i=1;i<=n;i++)
        d[i]={(int)0,(int)1e18};
    d[1]={0,0};
    q.push({d[1],1});
    while(!q.empty())
    {
        auto [w,x]=q.top();
        q.pop();
        if(use[x])
            continue;
        use[x]=1;
        for(auto [v,e]:g[x])
        {
            if(d[v]<d[x]+e)
            {
                d[v]=d[x]+e;
                q.push({d[v],v});
            }
        }
    }
    double ans=0;
    for(int x=1;x<=n;x++)
        for(auto [y,e]:g[x])
        {
            {
                int r=p-d[x].d*2;
                double s=d[x].s*2;
                if(r>=0)
                    ans=max(ans,1.0*r*e.s/e.d+s);
            }
            {
                int r=p-d[x].d-d[y].d-e.d;
                double s=d[x].s+d[y].s+e.s;
                if(r>=0)
                    ans=max(ans,1.0*r*e.s/e.d+s);
            }
        }
    cout<<fixed<<setprecision(15)<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12136kb

input:

3 3 4
1 2 1 1
2 3 2 4
3 1 1 1

output:

6.000000000000000

result:

ok - 1 values

Test #2:

score: 0
Accepted
time: 2ms
memory: 9548kb

input:

4 3 9
1 2 2 1
1 3 2 2
1 4 2 3

output:

13.500000000000000

result:

ok - 1 values

Test #3:

score: 0
Accepted
time: 2ms
memory: 9460kb

input:

4 3 5
1 2 10 1
2 3 2 100
1 4 3 10

output:

16.666666666666668

result:

ok - 1 values

Test #4:

score: 0
Accepted
time: 2ms
memory: 10788kb

input:

3 3 10
1 2 3 1
1 3 4 5
2 3 2 10

output:

22.000000000000000

result:

ok - 1 values

Test #5:

score: 0
Accepted
time: 4ms
memory: 12712kb

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.000000000000000

result:

ok - 1 values

Test #6:

score: 0
Accepted
time: 6ms
memory: 12228kb

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.000000000000000

result:

ok - 1 values

Test #7:

score: 0
Accepted
time: 0ms
memory: 12188kb

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.000000000000000

result:

ok - 1 values

Test #8:

score: 0
Accepted
time: 5ms
memory: 13356kb

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.000000000000000

result:

ok - 1 values

Test #9:

score: 0
Accepted
time: 3ms
memory: 11304kb

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.000000000000000

result:

ok - 1 values

Test #10:

score: 0
Accepted
time: 7ms
memory: 13004kb

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.000000000000000

result:

ok - 1 values

Test #11:

score: 0
Accepted
time: 6ms
memory: 11760kb

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.000000000000000

result:

ok - 1 values

Test #12:

score: 0
Accepted
time: 6ms
memory: 11748kb

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.000000000000000

result:

ok - 1 values

Test #13:

score: 0
Accepted
time: 0ms
memory: 12176kb

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.000000000000000

result:

ok - 1 values

Test #14:

score: 0
Accepted
time: 0ms
memory: 13136kb

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.000000000000000

result:

ok - 1 values

Test #15:

score: 0
Accepted
time: 2ms
memory: 9268kb

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.142857142856883

result:

ok - 1 values

Test #16:

score: 0
Accepted
time: 4ms
memory: 11452kb

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.000000000000000

result:

ok - 1 values

Test #17:

score: 0
Accepted
time: 0ms
memory: 9564kb

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.000000000000000

result:

ok - 1 values

Test #18:

score: -100
Wrong Answer
time: 3ms
memory: 11460kb

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.000000000000000

result:

wrong answer - (1st value) expected: 678182.0000000000000000, actual: 676510.0000000000000000