QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#764115 | #5336. Breakdown | Mispertion | 100 ✓ | 510ms | 9396kb | C++23 | 4.2kb | 2024-11-20 00:30:19 | 2024-11-20 00:30:20 |
Judging History
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