QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#764115#5336. BreakdownMispertion100 ✓510ms9396kbC++234.2kb2024-11-20 00:30:192024-11-20 00:30:20

Judging History

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

  • [2024-11-20 00:30:20]
  • 评测
  • 测评结果:100
  • 用时:510ms
  • 内存:9396kb
  • [2024-11-20 00:30:19]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
using ld = long double;
using pii = pair<int, int>;

#define F first
#define S second

const ld PI = 3.1415926535;
const int N = 305;
const int M = 1e7 + 1;
ll mod;
const int infi = 1e9;
const ll infl = 1e16;
const int P = 31;

int mult(int a, int b) { return a * 1LL * b % mod; }

int sum(int a, int b) {
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % (mod + 1);
    } else {
        ll b = binpow(a, n / 2);
        return b * b % (mod + 1);
    }
}

int n, k, w[N][N], d[N][N][3], d1[N][5], dn[N][5];
vector<pii> por;
vector<int> ans = {};

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> w[i][j];
        }
    }
    for(int i = 1; i <= n * n; i++){
        int u, v;
        cin >> u >> v;
        por.push_back({u, v});
    }
    reverse(por.begin(), por.end());
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            d[i][j][0] = d[i][j][1] = d[i][j][2] = infl;
    for(int i = 1; i <= n; i++){
        d1[i][3] = d1[i][4] = infl;
        dn[i][3] = dn[i][4] = infl;
    }
    for(auto e : por){
        int u = e.first, v = e.second;
        //1
        d[u][v][1] = w[u][v];
        //2
        for(int k = 1; k <= n; k++)
            d[k][v][2] = min(d[k][v][2], d[k][u][1] + d[u][v][1]), 
            d[u][k][2] = min(d[u][k][2], d[u][v][1] + d[v][k][1]);
        //3
        for(int k = 1; k <= n; k++){
            d1[k][3] = min(d1[k][3], d[1][u][1] + d[u][v][1] + d[v][k][1]);
            d1[v][3] = min(d1[v][3], d[1][k][1] + d[k][u][1] + d[u][v][1]);
        }
        if(u == 1){
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    d1[j][3] = min(d1[j][3], d[u][v][1] + d[v][i][1] + d[i][j][1]);
        }
        
        for(int k = 1; k <= n; k++){
            dn[k][3] = min(dn[k][3], d[k][u][1] + d[u][v][1] + d[v][n][1]);
            dn[u][3] = min(dn[u][3], d[u][v][1] + d[v][k][1] + d[k][n][1]);
        }
        if(v == n){
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    dn[i][3] = min(dn[i][3], d[i][j][1] + d[j][u][1] + d[u][v][1]);
        }

        //4
        for(int k = 1; k <= n; k++){
            d1[k][4] = min(d1[k][4], d[1][u][1] + d[u][v][1] + d[v][k][2]);
            d1[k][4] = min(d1[k][4], d[1][u][2] + d[u][v][1] + d[v][k][1]);
            d1[v][4] = min(d1[v][4], d[1][k][1] + d[k][u][2] + d[u][v][1]);
        }
        if(u == 1){
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    d1[j][4] = min(d1[j][4], d[u][v][1] + d[v][i][2] + d[i][j][1]);
        }

        for(int k = 1; k <= n; k++){
            dn[k][4] = min(dn[k][4], d[k][u][2] + d[u][v][1] + d[v][n][1]);
            dn[k][4] = min(dn[k][4], d[k][u][1] + d[u][v][1] + d[v][n][2]);
            dn[u][4] = min(dn[u][4], d[u][v][1] + d[v][k][2] + d[k][n][1]);
        }
        if(v == n){
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    dn[i][4] = min(dn[i][4], d[i][j][1] + d[j][u][2] + d[u][v][1]);
        }
        int x = k / 2;
        int y = k - x;
        int ret = infl;
        for(int i = 1; i <= n; i++){
            int a, b;
            if(x <= 2)
                a = d[1][i][x];
            else
                a = d1[i][x];
            if(y <= 2)
                b = d[i][n][y];
            else
                b = dn[i][y];
            ret = min(ret, a + b);
        }
        ans.push_back(ret);
    }
    ans.pop_back();
    reverse(ans.begin(), ans.end());
    for(auto e : ans)
        cout << (e >= infl ? -1 : e) << '\n';
    cout << -1 << '\n';
}

signed main() {
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 7.14286
Accepted
time: 1ms
memory: 5780kb

input:

3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2

output:

11
18
22
22
22
-1
-1
-1
-1

result:

ok 9 lines

Test #2:

score: 7.14286
Accepted
time: 510ms
memory: 9272kb

input:

300 2
79080983 43940140 68715596 60635497 34516232 76599971 73652832 48802380 79047488 70548768 72272603 33233301 24596085 41145540 58317573 4313140 17545576 36498983 43917291 64241186 4543357 12075264 89054532 73639238 3789913 22531781 67724591 11967943 28427616 93940948 96393338 11943968 9277009 1...

output:

3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416388
3416...

result:

ok 90000 lines

Test #3:

score: 7.14286
Accepted
time: 499ms
memory: 9164kb

input:

300 3
83957611 35325593 88681722 41466809 46504193 29254422 77081598 91453131 80522092 2513914 40289962 84795019 86832248 14215649 31454869 87489118 83035560 67312015 43615707 85920407 30285760 67973762 21037915 39738950 38015599 92436066 9771422 24214681 12686143 2653177 73477292 57548322 32921980 ...

output:

5519541
6275027
6552320
7297778
7346934
7498181
7657114
7928366
7957391
8189457
8518341
8757640
9181549
9806421
9861669
9914149
10015972
10153884
10634795
10759759
10815313
10908143
11255622
11570702
11799297
11875439
12369445
12826869
12907710
12931889
12989034
13069837
13247693
13330540
13354046
1...

result:

ok 90000 lines

Test #4:

score: 7.14286
Accepted
time: 499ms
memory: 9240kb

input:

300 3
68643256 70632134 16897922 50985321 65651145 43932467 16347530 70713085 32317288 24721518 26758751 46902072 12809144 34201253 22158381 43744551 42333311 82649067 76219957 62924164 44590081 32608440 72010262 15392918 38594983 80639486 49698279 70754361 55448259 81236143 82261366 81710642 492946...

output:

7111913
7426027
8029288
8670936
9156123
9242253
9602204
10155159
10158363
10650558
10675458
11268236
11467997
11823495
12038301
12340024
12359083
12428699
13543380
13735928
14204961
14224177
14224936
14251448
14438756
14530329
14728521
14752281
15024734
15178429
15216342
15225967
15390887
15653611
1...

result:

ok 90000 lines

Test #5:

score: 7.14286
Accepted
time: 499ms
memory: 9256kb

input:

300 4
13929316 80864958 82545639 85843063 53089681 45934666 84444169 77283048 93358015 68323740 44616305 79104671 76828369 66788872 94793933 950160 78345654 84569169 29947932 16360493 8847052 61729858 21204400 73661983 71531607 34295422 63694079 12468602 16268938 74465322 26539455 56354690 67942611 ...

output:

3969579
4566168
5255407
5499553
5808348
5921229
5972155
6369171
6763238
6781437
7372916
7415572
7476196
7725026
7727378
8191691
8202001
8288256
8339881
8760753
8771510
9007562
9034459
9109318
9192593
9271365
9293180
9361165
9379075
9411132
9449356
9480728
9512362
9515852
9577321
9636404
9647069
9680...

result:

ok 90000 lines

Test #6:

score: 7.14286
Accepted
time: 507ms
memory: 9168kb

input:

300 4
76708747 42846922 83665124 94087125 37491307 7535982 44867920 59728721 69916991 5592346 24574466 63237454 53933754 98388464 60484770 54585967 2754885 21530530 73581833 64319619 77465805 90468309 70259676 87424451 23960454 92231294 34125211 31603216 18365914 29854039 95579763 5444524 87921862 4...

output:

5022438
5142609
5209002
5384593
5459290
5538809
5726318
5760192
5857608
6049986
6688758
6875975
6878946
7099889
7315025
7425679
7479639
7589978
7649850
7650840
7768742
7816399
7839976
7895467
7989611
8006278
8103336
8124972
8165926
8235664
8290712
8375728
8407478
8442320
8464366
8529666
8563900
8590...

result:

ok 90000 lines

Test #7:

score: 7.14286
Accepted
time: 509ms
memory: 9332kb

input:

300 5
59306160 36889797 27798007 3905092 40685780 20251544 77674088 39683421 31120783 59574808 4812361 41021807 56359467 79194843 68334473 98698309 96589696 78766472 25516973 77061633 14758988 77654840 29616379 69008391 14360340 28052925 9547456 62809414 99979065 54046904 3275889 29201148 21019838 5...

output:

4211397
4396375
4537940
4559861
4587072
4709688
4724290
4748609
4833555
4840188
4848955
4882876
4920176
4968670
5179411
5352544
5461526
5467935
5478611
5486727
5504271
5680819
5705283
5940904
5948175
5977572
5984748
6009281
6024571
6048283
6061150
6118248
6126178
6160748
6216232
6219672
6231172
6262...

result:

ok 90000 lines

Test #8:

score: 7.14286
Accepted
time: 505ms
memory: 9160kb

input:

300 5
47736149 88861034 10810331 17013588 60036457 69152448 48957489 78526318 68989757 97386955 41411181 86708494 92447806 52123792 60249438 46796131 24764687 91402590 85219769 38920970 33608244 57441221 21926838 91371336 96897852 219307 73989994 14209435 46782787 60647271 87059466 12265190 83185022...

output:

2345333
2353314
2677695
2801044
2908509
3167704
3634682
3779205
3802549
3930467
3938268
3962463
4082749
4138575
4160486
4182813
4210763
4240897
4279641
4305808
4341546
4404483
4444615
4482328
4520468
4549852
4601330
4621183
4715636
4774831
4775042
4807534
4828106
4872804
4880383
4902586
4911831
4978...

result:

ok 90000 lines

Test #9:

score: 7.14286
Accepted
time: 498ms
memory: 9276kb

input:

300 6
44556671 88953181 8051327 32397369 37922556 15995799 73491582 57217602 9540021 52648508 53802281 58468594 92598009 89704054 7510364 45210334 13781981 15286145 57827567 68324540 32205273 49853369 60337630 44065599 44775659 98814845 47274617 45736973 57153811 71243991 93654713 64112770 24940473 ...

output:

2955339
3005655
3111127
3139616
3373777
3542224
3596810
3717593
3756829
3879255
3892200
3896948
3922522
3972115
3980479
3985746
4000443
4027846
4117766
4118092
4161317
4198385
4244934
4261213
4273433
4277351
4338970
4339374
4347518
4355248
4381430
4382577
4448028
4529481
4532319
4572316
4581184
4678...

result:

ok 90000 lines

Test #10:

score: 7.14286
Accepted
time: 507ms
memory: 9212kb

input:

300 6
91571466 75209854 89128933 37143873 23686514 83371165 89428702 25970161 45367154 93235195 45229065 66856010 55236865 58423787 68261393 17617253 16957680 52365367 67931481 519532 45620347 80642623 12907721 11231077 45638607 37303986 49495732 41364535 27737542 48508942 31857396 73744794 91918173...

output:

3085731
3994780
4301250
4354486
4808534
4869013
4988109
5067076
5259726
5453104
5473203
5524486
5706230
5728562
5786562
5805177
5917541
5985609
6071013
6081365
6139906
6161317
6232173
6399843
6438859
6482300
6534124
6607048
6683663
6747229
6755990
6933017
6949601
6982507
7041525
7075633
7075924
7097...

result:

ok 90000 lines

Test #11:

score: 7.14286
Accepted
time: 505ms
memory: 9396kb

input:

300 7
24940224 83645521 36379740 28413880 26559758 86040909 59930274 49070664 71627603 29904665 54893166 91657821 79979185 58760958 18496929 30258413 63171198 48165765 64364685 76873602 81192779 17775654 57570806 37952981 77679698 31499356 69837209 87976441 5673618 98729540 85165383 16609964 7139571...

output:

3131569
3285731
3654143
3732194
3825245
3906433
3913375
3977102
3984159
4043737
4077852
4080104
4115196
4116598
4252797
4292040
4363844
4658179
4675039
4692908
4732888
4771630
4799487
4853856
4907592
4929288
4967595
5007143
5014963
5016430
5086576
5100996
5109248
5124421
5211790
5232573
5277003
5359...

result:

ok 90000 lines

Test #12:

score: 7.14286
Accepted
time: 509ms
memory: 9260kb

input:

300 7
37459612 91481479 57187570 10691844 20838340 62598989 28897713 53674263 11657266 60931974 9326222 86004186 83534243 30941644 52438647 11073921 84815222 52970601 63982797 28884238 54890579 38592602 27010340 9703359 10206309 91165092 98672034 89282207 4369528 71414208 77885587 86881751 19184563 ...

output:

2852676
3244351
3282291
3663761
3763086
3817611
3866044
3902489
3989085
4064417
4125836
4157436
4199216
4207465
4229258
4257378
4260566
4300625
4305369
4316637
4317838
4364246
4366355
4393774
4407941
4452664
4501475
4510824
4591202
4597962
4600227
4630995
4679458
4681057
4690834
4737625
4738434
4739...

result:

ok 90000 lines

Test #13:

score: 7.14286
Accepted
time: 504ms
memory: 9284kb

input:

300 8
58374321 80707659 67362321 50588391 77235043 98369690 16540397 36868027 68501476 7136155 65680629 58382975 54852527 71353783 56019174 14036942 16262986 24318796 73871157 5499796 57170070 12207508 37650508 26972162 16454937 40427532 88923433 62636877 49796631 17689379 6900086 29598184 30658020 ...

output:

3761369
3986667
4027543
4041656
4231721
4543071
4549998
4589798
4839024
4859587
4936834
4983960
5003120
5108549
5135991
5151832
5175927
5206408
5249725
5253446
5308513
5353829
5354268
5534526
5548553
5569106
5687291
5693657
5705767
5727079
5737742
5737881
5859342
5863350
5892076
5896135
5934474
5940...

result:

ok 90000 lines

Test #14:

score: 7.14286
Accepted
time: 500ms
memory: 9320kb

input:

300 8
59886188 67188057 99493133 12175767 96775930 34561383 59209355 86344913 13933118 56335849 29745006 24843931 87487514 34144728 33340407 10758636 15892741 32808587 25227735 72595590 900646 96740985 56936550 6784745 97002052 10389200 33649989 56431566 30682286 77575417 70270738 71958268 80925687 ...

output:

4238183
4271286
4277627
4300711
4322141
4454331
4567970
4645558
4732939
4872092
4900742
4950198
5009263
5064282
5100486
5109685
5193894
5314427
5362402
5394576
5409841
5422832
5467438
5471984
5481431
5534967
5536883
5553270
5590230
5665620
5666720
5750301
5759829
5795552
5797675
5807742
5916860
5918...

result:

ok 90000 lines