QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#878782#9696. Analysisucup-team3584#WA 235ms64240kbC++174.1kb2025-02-01 17:39:252025-02-01 17:39:27

Judging History

This is the latest submission verdict.

  • [2025-02-06 00:45:32]
  • hack成功,自动添加数据
  • (/hack/1517)
  • [2025-02-01 17:39:27]
  • Judged
  • Verdict: WA
  • Time: 235ms
  • Memory: 64240kb
  • [2025-02-01 17:39:25]
  • Submitted

answer

#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> using vvvc = vector<vector<vector<T>>>;
template<class T> using pq = priority_queue<T,vector<T>,greater<T>>;
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }

int dx4[] = {1,0,-1,0};
int dy4[] = {0,1,0,-1};

#define overload5(a, b, c, d, e, name, ...) name
#define overload4(a, b, c, d, name, ...) name
#define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf)
#define REP1(i, n) for(ll i = 0; i < (n); ++i)
#define REP2(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)
#define per1(i, n) for(ll i = (n)-1; i >= 0; --i)
#define per2(i, a, b) for(ll i = (a)-1; i >= b; --i)
#define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define drop(s) cout << #s << endl, exit(0)
#define si(c) (int)(c).size()
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
#define rng(v, l, r) v.begin() + (l), v.begin() + (r)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define SORT(v) sort(all(v))
#define REV(v) reverse(all(v))
#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define overload2(_1, _2, name, ...) name
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))

ll inf = 1001001001001001001;

ll dp[500500][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,A,B;
    cin >> N >> A >> B;
    chmin(A,B);
    vvc<int>ki(N);
    rep(i,N-1) {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        ki[u].pb(v);
        ki[v].pb(u);
    }
    auto dfs = [&](auto &dfs,int n,int p) -> void {
        vc<ll>res;
        ll sum = 0,mi = inf;
        for(auto i:ki[n]) {
            if(i == p) continue;
            dfs(dfs,i,n);
            ll mi1 = inf;
            rep(j,3) {
                chmin(mi1,dp[i][j]+A);
            }
            chmin(mi,dp[i][1]-dp[n][2]);
            chmin(mi,dp[i][0]-dp[n][2]);
            ll mi2 = inf;
            chmin(mi2,dp[i][0]+B);
            chmin(mi2,dp[i][2]+B);
            chmin(mi2,dp[i][1]);
            res.pb(mi2-mi1);
            sum += mi1;
        }
        dp[n][0] = dp[n][1] = dp[n][2] = inf;
        chmin(dp[n][2],sum);
        chmin(dp[n][0],sum+max(0ll,mi));
        SORT(res);
        rep(i,si(res)) {
            sum += res[i];
            chmin(dp[n][(i+1)%2],sum-((i+1)/2)*B);
        }
    };
    dfs(dfs,0,-1);
    cout << min({dp[0][0]-B,dp[0][1]-B,dp[0][2]}) << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 100 1000
1 2
2 3
3 4
4 5

output:

0

result:

ok 1 number(s): "0"

Test #2:

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

input:

5 100 200
1 2
1 3
2 4
2 5

output:

100

result:

ok 1 number(s): "100"

Test #3:

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

input:

10 133494816 109943166
10 8
5 3
1 2
8 9
8 5
2 4
8 7
8 6
10 1

output:

219886332

result:

ok 1 number(s): "219886332"

Test #4:

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

input:

10 165074331 854297934
6 2
2 7
9 8
2 9
9 10
6 3
6 4
5 6
6 1

output:

825371655

result:

ok 1 number(s): "825371655"

Test #5:

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

input:

9 719441223 227056392
4 6
9 2
5 3
1 4
6 8
1 9
1 7
3 1

output:

227056392

result:

ok 1 number(s): "227056392"

Test #6:

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

input:

10 216399993 137522662
9 6
1 2
2 9
4 1
10 3
7 5
5 4
3 7
2 8

output:

137522662

result:

ok 1 number(s): "137522662"

Test #7:

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

input:

10 796722415 144928611
9 10
6 4
2 7
5 1
3 2
6 5
3 9
1 8
6 3

output:

289857222

result:

ok 1 number(s): "289857222"

Test #8:

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

input:

9 377925753 230747764
1 3
8 5
5 1
6 8
7 2
7 4
6 7
7 9

output:

230747764

result:

ok 1 number(s): "230747764"

Test #9:

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

input:

1000 322954853 561443729
978 218
369 277
32 327
665 398
950 674
723 693
426 803
188 866
857 272
644 704
419 303
884 872
178 742
884 903
499 104
832 692
585 636
215 68
369 911
672 796
908 852
971 948
497 825
319 193
524 845
94 651
669 210
529 963
326 877
56 310
707 447
722 388
881 945
605 757
140 521...

output:

156210605808

result:

ok 1 number(s): "156210605808"

Test #10:

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

input:

1000 921029898 839745690
143 605
601 220
606 11
722 857
603 448
328 773
696 504
524 68
247 119
416 398
646 956
864 414
727 136
156 354
182 559
286 928
439 312
57 849
48 348
559 563
417 982
769 868
179 915
40 480
396 979
377 716
226 177
996 395
188 977
692 634
183 349
581 36
787 227
891 850
73 137
90...

output:

277955823390

result:

ok 1 number(s): "277955823390"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

970 865003183 730298972
199 701
485 267
822 192
167 635
636 848
438 566
924 5
11 222
576 420
509 432
428 630
251 832
860 510
306 299
147 817
190 764
126 413
693 156
546 72
672 868
929 312
513 260
920 803
112 947
302 316
875 615
566 587
321 369
889 645
819 692
255 735
450 523
824 397
509 300
167 353
...

output:

240998660760

result:

ok 1 number(s): "240998660760"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

1000 862859507 141216120
116 532
374 648
795 283
346 28
787 724
336 17
936 385
293 829
704 161
1 816
2 483
931 82
417 565
828 451
774 276
476 401
447 696
234 769
930 847
496 578
458 536
226 301
244 902
682 977
738 657
337 39
235 124
571 751
364 50
88 556
54 444
804 352
96 120
642 970
533 213
740 776...

output:

33609436560

result:

ok 1 number(s): "33609436560"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

1000 558366571 505493045
489 545
912 759
682 374
19 582
343 297
393 769
440 361
589 29
12 393
253 348
190 323
286 193
221 42
453 593
310 638
966 761
646 780
292 401
123 31
695 515
846 802
436 471
232 594
198 650
834 242
17 301
775 942
475 41
332 535
64 479
760 766
752 150
591 195
310 712
536 416
560...

output:

119801851665

result:

ok 1 number(s): "119801851665"

Test #14:

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

input:

970 935970558 426067204
636 310
658 635
469 629
615 193
346 166
256 932
847 1
301 697
106 259
645 352
240 79
102 908
873 617
625 354
887 209
876 525
354 543
843 369
348 90
264 892
232 31
752 934
88 730
670 957
722 575
606 650
410 468
720 603
785 351
109 528
467 58
239 504
107 806
402 533
961 660
315...

output:

100551860144

result:

ok 1 number(s): "100551860144"

Test #15:

score: 0
Accepted
time: 203ms
memory: 42924kb

input:

500000 854171423 776249842
139098 351774
367457 487287
175143 435875
131857 395707
160145 78070
430794 234221
196215 268128
238673 209485
102068 166268
13331 411244
123088 54536
113149 55054
463338 308892
144261 442906
194976 240811
392302 303426
56316 276955
223558 229936
354466 364582
175540 30642...

output:

129178064956746

result:

ok 1 number(s): "129178064956746"

Test #16:

score: 0
Accepted
time: 203ms
memory: 42472kb

input:

493243 273965898 224990156
218586 487842
169177 471606
145650 330516
368949 418196
244612 431071
417446 407540
225235 182582
481785 387884
188870 368395
117071 290711
75134 22877
294614 91575
215711 163402
91686 127432
337291 433398
480599 365175
187020 292618
210054 164142
317950 488724
232843 3021...

output:

37049578968832

result:

ok 1 number(s): "37049578968832"

Test #17:

score: 0
Accepted
time: 199ms
memory: 42080kb

input:

488126 782505765 760857298
290095 354815
401202 249622
116534 461355
15189 354691
48189 411672
68619 226381
103976 450020
273367 131977
367786 400433
76697 111085
211550 315456
372878 125870
126388 467891
147731 64354
248125 228698
138125 298745
172808 241811
193855 454527
117671 17601
109584 153374...

output:

123697896936946

result:

ok 1 number(s): "123697896936946"

Test #18:

score: 0
Accepted
time: 204ms
memory: 42980kb

input:

500000 466056790 251466232
299560 359515
8444 202278
307923 223463
288862 295421
111000 434937
412214 423184
301363 243058
269095 62467
335738 88086
340322 169116
34205 395799
405652 250981
105714 220549
87849 169294
277687 429426
225867 46568
450624 91701
42645 216689
394332 384787
438993 222565
18...

output:

41870384959160

result:

ok 1 number(s): "41870384959160"

Test #19:

score: 0
Accepted
time: 200ms
memory: 42496kb

input:

493243 573252828 66338508
419359 306156
251109 152438
26779 97738
309450 296418
373858 396418
448991 22564
430724 185463
299545 425898
437084 78551
139638 404678
111173 175392
297708 440989
89818 243571
399226 400780
489097 281923
11028 367193
333327 453026
176869 224530
39615 472178
206594 195606
1...

output:

10889399749692

result:

ok 1 number(s): "10889399749692"

Test #20:

score: 0
Accepted
time: 201ms
memory: 42060kb

input:

488126 972949106 602615933
388528 63391
9531 33183
212757 36927
438731 436006
422330 405413
146853 165100
162875 69347
23332 471508
413579 53583
189773 168863
474346 401848
227727 145742
275253 469471
90147 449351
25157 120955
75658 402250
324537 298973
437165 279589
452249 7884
355052 384472
123287...

output:

98051638458430

result:

ok 1 number(s): "98051638458430"

Test #21:

score: 0
Accepted
time: 196ms
memory: 42972kb

input:

500000 90278906 978879417
358944 493867
493203 354507
409295 98147
389389 125183
162034 468622
163783 39977
415208 82592
156372 265725
345117 427435
118503 471786
99375 284747
487964 319889
474855 206569
210299 134145
259364 205684
359379 56978
164073 297096
64233 393022
294365 279170
376041 55007
1...

output:

42920682975858

result:

ok 1 number(s): "42920682975858"

Test #22:

score: 0
Accepted
time: 190ms
memory: 42464kb

input:

493243 164511686 350222869
351340 191153
257437 219475
186001 139530
278269 58222
141088 266162
398687 314887
157147 323783
284264 276082
316903 377534
350080 362349
40374 172179
130676 82807
480735 340213
234038 214618
68128 372560
16620 237171
478361 435079
305559 216465
289154 340529
375728 41543...

output:

44227111495753

result:

ok 1 number(s): "44227111495753"

Test #23:

score: 0
Accepted
time: 183ms
memory: 42056kb

input:

488126 642159129 263370959
44552 197898
380080 206537
140639 308594
351992 135380
303166 218985
319796 49060
371374 453664
428 54617
358405 391069
171321 139233
63966 412768
305919 69678
277241 132674
180726 167736
289829 271113
81408 179599
447573 400106
318645 183780
154531 336450
95541 147756
401...

output:

42886010108765

result:

ok 1 number(s): "42886010108765"

Test #24:

score: 0
Accepted
time: 224ms
memory: 42964kb

input:

500000 227011278 258113320
150514 294451
342069 271893
227231 60619
82319 461337
353846 27080
309227 268626
411701 341851
358318 70115
173596 218285
370583 147976
406854 145088
327492 376583
3032 114161
142843 193518
66416 172422
202866 142251
386532 48596
435443 180733
402607 185183
229353 413454
2...

output:

40851635835622

result:

ok 1 number(s): "40851635835622"

Test #25:

score: 0
Accepted
time: 205ms
memory: 42476kb

input:

493243 510705235 42511833
87213 53346
395712 237497
90517 390397
293097 248152
294155 64543
178086 222294
229487 268433
483631 39269
7850 317508
439454 120814
192520 401441
444658 50968
451109 274890
98724 235515
134729 21163
227243 322710
476012 269884
409731 327526
278902 438427
487503 207748
1194...

output:

6984694161900

result:

ok 1 number(s): "6984694161900"

Test #26:

score: 0
Accepted
time: 202ms
memory: 42060kb

input:

488126 166787474 973519288
204498 464724
181062 483851
479357 456480
206403 440644
232879 290994
390552 360035
287461 427161
15469 271720
288093 209214
71051 55727
155229 165866
337543 156901
256178 481787
182424 96066
131477 124603
32360 188260
107899 377254
144321 327566
208052 248502
372079 31814...

output:

68184480959238

result:

ok 1 number(s): "68184480959238"

Test #27:

score: 0
Accepted
time: 225ms
memory: 59740kb

input:

500000 546642225 514886198
266319 28043
158794 417039
440908 430915
295758 232676
231586 456539
194465 7853
64307 421864
34221 123187
426684 457948
180136 442509
150780 53443
467434 467264
68143 444542
119170 210212
149553 10228
499095 261944
422381 419380
416490 365218
121678 107135
481516 265616
1...

output:

61771926946456

result:

ok 1 number(s): "61771926946456"

Test #28:

score: 0
Accepted
time: 222ms
memory: 64240kb

input:

493243 370794558 196606168
216801 307879
256784 177817
222429 482684
14929 213651
234581 433081
305369 421870
197764 214920
101579 340494
236438 444628
45593 72185
113882 52613
178280 162949
380787 101906
426446 22696
469809 24949
140675 467549
449640 321175
169706 436150
88105 147991
69447 41826
18...

output:

23346589237664

result:

ok 1 number(s): "23346589237664"

Test #29:

score: 0
Accepted
time: 212ms
memory: 61732kb

input:

488126 451052716 977924751
455340 142885
7662 191589
165810 57052
299322 419789
174196 146375
341124 362442
257346 247085
254051 210826
123445 215436
118302 43614
142968 323638
479006 381080
49138 432732
448248 75475
73466 11978
73897 427427
296389 195838
202874 407604
59800 34418
337854 260783
1639...

output:

82454230696712

result:

ok 1 number(s): "82454230696712"

Test #30:

score: -100
Wrong Answer
time: 235ms
memory: 57592kb

input:

500000 91438100 530608995
446576 217053
207712 485354
315736 457894
144572 88174
228249 209130
144829 203072
416363 149949
414353 349684
351555 210955
191135 33272
51974 455326
381419 470762
393127 276438
457867 399254
44115 168811
295361 256453
172919 465608
204954 205042
118231 186091
411786 46533...

output:

25750512832370

result:

wrong answer 1st numbers differ - expected: '25750421394270', found: '25750512832370'