QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#8628 | #1062. 世界地图 | Qingyu | 100 ✓ | 694ms | 67348kb | C++20 | 4.2kb | 2021-04-03 11:27:53 | 2021-12-19 10:39:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
unsigned int SA, SB, SC;
int lim;
int n, m;
int ex[10010][105], ey[10010][105];
int getweight()
{
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC % lim + 1;
}
void gen()
{
scanf("%d%d%u%u%u%d", &n, &m, &SA, &SB, &SC, &lim);
int i, j, w;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
w = getweight();
ex[j][i] = w;
}
for (i = 1; i < n; i++)
for (j = 1; j <= m; j++)
{
w = getweight();
ey[j][i] = w;
}
}
typedef long long ll;
struct edge
{
int u, v, w;
edge(int a, int b, int c) : u(a), v(b), w(c) {}
bool operator < (const edge B) const {
return w < B.w;
}
};
int id(int x, int y)
{
return (x - 1) * n + y;
}
int key[1000100], f[1000100];
int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
ll kruskal(vector<edge> &a, vector<edge> &b)
{
ll ans = 0;
sort(a.begin(), a.end());
b.clear();
for (int i = 0; i < a.size(); ++i)
{
int fu = find(a[i].u), fv = find(a[i].v);
if (fu == fv)
ans += a[i].w;
else
{
if (key[fu] && key[fv])
f[fu] = fv, b.push_back(edge(fu, fv, a[i].w));
else if (key[fu])
f[fv] = fu;
else
f[fu] = fv;
}
}
return ans;
}
vector<edge> pre[10010], suf[10010];
ll pres[10010], sufs[10010];
void upt(int x, int op)
{
f[x] = x;
key[x] = op;
}
vector<edge> a, b;
void getPre()
{
a.clear();
for (int i = 1; i <= n * m; ++i)
f[i] = i, key[i] = 0;
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
upt(id(i, j), 1);
upt(id(1, j), 1);
if (i > 2)
upt(id(i - 1, j), 0);
}
for (int j = 1; j <= n; ++j)
{
if (i != 1)
{
a.push_back(edge(id(i, j), id(i - 1, j), ex[i - 1][j]));
pres[i] += ex[i - 1][j];
}
if (j != n)
{
a.push_back(edge(id(i, j), id(i, j + 1), ey[i][j]));
pres[i] += ey[i][j];
}
}
ll del = kruskal(a, b);
pres[i] += pres[i - 1] - del;
pre[i] = b;
a = b;
}
}
void getSuf()
{
a.clear();
for (int i = 1; i <= n * m; ++i)
f[i] = i, key[i] = 0;
for (int i = m; i >= 1; --i)
{
for (int j = 1; j <= n; ++j)
{
upt(id(i, j), 1);
upt(id(m, j), 1);
if (i < m - 1)
upt(id(i + 1, j), 0);
}
for (int j = 1; j <= n; ++j)
{
if (i != m)
{
a.push_back(edge(id(i, j), id(i + 1, j), ex[i][j]));
sufs[i] += ex[i][j];
}
if (j != n)
{
a.push_back(edge(id(i, j), id(i, j + 1), ey[i][j]));
sufs[i] += ey[i][j];
}
}
ll del = kruskal(a, b);
sufs[i] += sufs[i + 1] - del;
suf[i] = b;
a = b;
}
}
int l, r, q;
int main()
{
gen();
getPre();
getSuf();
scanf("%d", &q);
while (q--)
{
a.clear();
scanf("%d %d", &l, &r);
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
a.push_back(edge(id(1, i), id(m, i), ex[m][i]));
upt(id(1, i), 0);
upt(id(m, i), 0);
upt(id(l - 1, i), 0);
upt(id(r + 1, i), 0);
ans += ex[m][i];
}
for (int i = 0; i < pre[l - 1].size(); ++i)
a.push_back(pre[l - 1][i]);
for (int i = 0; i < suf[r + 1].size(); ++i)
a.push_back(suf[r + 1][i]);
ll del = kruskal(a, b);
ans += pres[l - 1] + sufs[r + 1] - del;
printf("%lld\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 5ms
memory: 10388kb
input:
50 50 858397672 21575781 421714252 50 50 10 30 25 41 10 44 41 45 47 47 39 42 20 38 28 47 12 15 26 32 9 25 18 26 7 15 5 8 7 31 8 37 41 42 18 21 32 32 14 35 6 22 12 26 42 45 9 23 14 14 5 6 8 24 25 43 37 38 15 46 26 43 35 48 22 30 20 45 21 49 11 12 6 46 15 45 21 43 4 40 4 18 28 37 32 38 18 26 32 32 10 48 2 48 5 34 31 43 34 36
output:
21046 24218 11414 32468 35179 33298 22126 22012 33300 30838 23977 29055 29918 33069 18185 14871 34615 32954 35312 20094 24226 25181 33130 25535 35374 34492 24067 22758 34675 13257 23443 26215 29241 17292 15165 34743 7157 13953 19672 9730 25603 29117 31267 29055 35312 8400 2536 14565 27209 33993
result:
ok 50 lines
Test #2:
score: 10
Accepted
time: 452ms
memory: 67132kb
input:
100 10000 753738892 852022308 109208427 5 10000 6068 9618 3347 9710 3237 5987 428 8918 183 2017 3654 8017 6218 8094 1812 4054 783 4265 638 6139 1780 6091 1559 1706 6627 8952 2958 6234 6213 8049 1860 9764 988 8148 4992 5669 7214 9591 4245 8494 5417 9671 2840 4466 5799 8328 5436 7160 1136 1170 3134 3854 1617 7378 5572 7923 290 1670 1759 3094 3154 8765 4656 5659 7172 8906 4704 4872 8285 8932 217 7528 5867 9160 460 9532 2806 8370 5088 7352 2700 8124 5230 8677 3570 7129 3141 8070 2987 6433 5357 5938 ...
output:
1211623 682743 1361117 283679 1533910 1058719 1526089 1457348 1224581 844519 1068307 1850478 1441600 1262311 1533505 393355 533670 1750612 1431335 1079803 1078983 1572722 1403657 1554603 1871623 1742851 796103 1436810 1618909 1627701 824187 1689150 1552343 1846414 1756497 505159 1260003 174270 833034 1453083 859321 1230906 1209937 952291 1230343 1768668 1679584 1494297 1458908 1439931 488949 1023647 1775172 1614892 1560785 407804 1827804 1033359 1856020 357064 618378 1096251 1302867 1292246 1371...
result:
ok 10000 lines
Test #3:
score: 10
Accepted
time: 447ms
memory: 67208kb
input:
100 10000 252296658 470686114 738681417 5 10000 19 9941 4573 8431 1956 8010 6495 7523 1584 9576 3805 7368 945 8568 753 6106 3261 6017 4137 4690 8260 8284 3732 7371 2222 9531 174 6288 4011 4548 7675 8100 787 5858 3504 4912 5358 9086 492 8450 4746 5765 2833 5471 6990 8945 4020 8049 2168 5355 4144 7941 882 6725 2058 8188 1534 6397 1937 6671 2184 5925 5327 5615 7035 9121 1549 4733 2231 5708 2683 9520 6292 8399 80 882 1987 8497 6520 6655 8288 9510 1766 2086 1928 9152 5227 9029 2017 2574 612 9073 2537...
output:
14776 1154093 741074 1685175 377030 1209281 446018 873015 1360987 1773494 1873502 1195181 505818 729771 1776734 1797785 925822 1613267 1178272 383399 1687330 1382812 1510227 1121331 1279314 1165058 781005 726730 964577 989349 1175799 1824181 1485743 1279135 1225339 594598 1482362 1727286 655503 1852727 1648219 1817645 521466 1164368 1772874 288905 1136667 499685 651159 1859933 1671942 853737 1268698 832744 1434847 939209 1665779 1669517 823817 984580 1125794 1190593 1790147 1449177 1790047 14361...
result:
ok 10000 lines
Test #4:
score: 10
Accepted
time: 121ms
memory: 11536kb
input:
1 10000 171380702 78283356 95463589 1000000000 300000 2866 9527 1368 3641 8547 9622 1710 5284 3041 9484 984 9571 2839 3647 5663 8848 8026 8600 7300 9784 510 4151 3111 9321 4378 4895 990 5806 2438 3661 1680 4894 1629 3165 1982 5285 2889 7265 387 3227 669 1395 5546 6488 74 3424 270 6207 509 518 279 9156 620 5467 3843 4151 2549 8989 6163 9761 5682 8456 2669 7970 6233 9005 3129 9388 4995 7139 2871 7893 6708 7419 1351 8898 264 2409 3 6737 4880 7800 1037 4663 2619 9203 2638 9424 6988 7982 1990 3815 92...
output:
1603289365972 3725016792897 4289545851500 3090001725177 1707389603747 677676134474 4428828830089 3243732939555 4519318185589 3605953230641 3076099184075 1812557746149 4530044194578 2505624713463 4229007401433 3264345621855 4057299323184 3225483188449 2697490604818 3434409901613 4438097816271 4329018830433 3192908400240 1950617638727 4788963195484 537123894238 2482606758983 4650158149170 1712843516412 3062670050586 3432246969014 2244394503826 3459653948720 1788063859971 3744681164067 237655922772...
result:
ok 300000 lines
Test #5:
score: 10
Accepted
time: 138ms
memory: 16560kb
input:
2 10000 274134852 279286565 744539633 1000000000 300000 1457 3215 5541 7081 6313 7973 670 4949 3425 8087 6139 6619 695 3800 7532 8343 5959 7017 6912 8042 7533 8728 1224 2877 359 6569 5752 5906 1720 3244 2070 3553 4732 8576 179 551 515 8656 1962 7775 2022 9067 690 2846 2047 2671 1137 8559 1349 7168 447 5261 7991 8798 8790 9859 2128 6743 144 4802 2836 4461 2313 3974 7686 8258 6455 8160 7832 9491 1136 9306 484 4819 3572 6459 7750 8976 4080 8956 882 1451 3916 7070 1344 3993 5752 8010 258 2796 2459 4...
output:
5477001280973 5611523257417 5537315630440 3794711171610 3535471770801 6323223914309 4580772497023 6102708394766 5945876722548 5885604544265 5849217345115 5546619600870 2512881639605 6527329416108 5637011461020 5663080665892 4091018500635 6399362487560 1230705483628 2774960893445 1966805369253 5206531479467 6226164022874 1707397404545 2779293321830 3433459529882 6109022386896 5920687597434 3569220449583 3545335270413 5548163608835 5537796880772 6261053700312 5505781796784 5541261788810 1202839711...
result:
ok 300000 lines
Test #6:
score: 10
Accepted
time: 131ms
memory: 16236kb
input:
2 10000 734766235 309378503 610268282 1000000000 300000 8879 9378 26 9684 6078 8954 7926 8887 4050 7388 951 5130 1991 3091 375 5194 242 1706 1669 1727 9485 9972 5638 8314 4679 5883 4955 6823 4621 7586 348 2348 420 2340 1001 8241 5672 6005 5238 6510 1604 9325 4921 7060 20 3348 3576 9918 7655 8802 2866 7291 3963 8844 3071 5671 4334 8373 408 769 528 1553 6556 8402 3207 7129 2171 6144 5051 7400 3070 4961 2312 7784 1044 1356 4292 5551 2345 3475 2208 6164 5808 6208 6377 9363 996 4292 4766 7620 1417 47...
output:
6316508944189 218298135044 4735457476186 6027486790948 4424182259889 3886123944524 5937796481642 3454065317288 5664230993454 6614047676609 6333322924341 4879394088851 5855623275532 5402516827740 4680300834131 5311810257921 5369465136126 1833940845223 6440262666077 5794652391437 1521847364172 5224681625772 4437857294039 2426098440868 5900276774031 3707333309883 3400853624849 4921938944743 3971929780147 6417381848293 5963459122698 5429123380898 4046888369512 4026814333610 5076773470557 54063515120...
result:
ok 300000 lines
Test #7:
score: 10
Accepted
time: 664ms
memory: 67348kb
input:
100 10000 784936363 827067061 800454511 1000000000 10000 2056 2962 5233 5350 1346 2099 8529 8825 2358 3371 3217 6419 1175 9635 2998 7699 1494 9244 2710 5459 1647 8372 6360 8398 1256 9955 1252 1473 4171 4704 4867 7373 3208 7839 2949 8996 4731 7531 8915 9536 2199 5546 2265 6448 1463 9131 2358 2383 6252 8586 3803 5511 4078 8448 1610 9440 1295 2818 3574 9966 2674 7302 5721 9089 484 551 2564 3514 845 1134 217 5146 1349 5960 5503 6349 508 1701 4743 8119 7671 8405 677 8245 4598 7192 2339 6257 1324 2821...
output:
218107916833770 236956297236591 221611594649234 232654372445039 215511117763537 163015473624889 37013079700783 127182022450125 54041351200568 173843674045542 78674875729514 191084774917088 31305721956998 234464326245872 227032500475120 179858820611878 128837146174236 94963670830748 172797399335623 224883721953769 159544704485008 139570501907820 56007526051194 239166503452671 183958297644251 198845593690849 135244713063038 52147897882585 203202149423677 86695735195146 128938169244012 159244180589...
result:
ok 10000 lines
Test #8:
score: 10
Accepted
time: 653ms
memory: 67168kb
input:
100 10000 72129929 485897764 129463885 1000000000 10000 383 7372 2861 4738 5799 7101 3570 9122 3175 4173 1444 7532 6191 9348 3164 6316 2122 4663 1589 2869 4784 7741 3529 5974 4792 7378 6016 8170 864 1289 1647 7570 293 1602 1054 8521 6193 9882 4543 5121 956 5006 1858 7086 4117 7517 9736 9847 7917 8654 1517 6887 7837 8197 845 8823 160 2707 4904 6538 3092 4911 4607 7516 2232 7999 6219 8682 1254 8023 552 3507 3441 4124 707 4934 621 3297 3816 6251 2653 8377 5171 6594 121 1009 932 1460 3310 3882 468 7...
output:
72090982299191 194600560760132 208326087759066 106457378837533 215695913806908 93645900885474 163942628341738 164031689768437 178662309764579 208841353815076 168610752734842 180880159627225 177470699352697 187964294311616 229294854382327 97557084520879 208227727138432 60656821171511 151175099594593 225644121724197 142515552524391 114238344597890 157953748850993 236841867770867 221905380356958 110878180260918 230937971916527 48416631529590 178529132278282 200376409780078 195983606524104 169710796...
result:
ok 10000 lines
Test #9:
score: 10
Accepted
time: 677ms
memory: 67260kb
input:
100 10000 963446001 261040754 78671748 1000000000 10000 1308 8621 2948 6287 2647 3069 103 5392 3204 9085 7669 8375 2823 5662 6455 7017 530 4194 567 9892 2436 9869 3149 6625 3015 7571 1051 1155 30 5077 1138 9673 8598 9184 5453 8895 902 7796 2749 5653 334 2677 4818 7123 2693 8574 1945 2913 6278 7799 662 8282 944 9923 54 8162 5604 8384 9312 9717 3458 7254 1931 2608 2767 9838 3319 6175 2531 5537 1990 7281 1317 4367 928 2960 3703 8655 8224 9199 4982 8873 3335 6151 3692 8746 4518 5741 1666 4553 3016 9...
output:
64264200768233 159631014825609 229412046850098 112894812377726 98703295232189 222675254882181 171598041130418 226137587624448 151655725634932 16103717296049 61433187417017 156336180363989 130459314798835 237120775693771 118682572200864 34995983081351 225547690108471 157054836420411 74239996440524 170021567189585 183470486188631 184341321206012 98654262321188 216293643205302 203125370280587 56913117851654 24361629340913 45240384392058 172905626711765 229904456965196 148697182443709 22336274058581...
result:
ok 10000 lines
Test #10:
score: 10
Accepted
time: 694ms
memory: 67168kb
input:
100 10000 64237141 422265017 577403465 1000000000 10000 1335 3887 3017 4150 13 5940 619 9252 2124 8016 6189 8581 3524 6793 5826 9716 880 1859 6383 6421 1312 3139 4259 6148 1005 2744 1353 8445 6463 9223 6923 9215 901 1803 1202 1820 1053 6563 3677 7206 7691 9391 4533 8068 4360 7698 4769 8394 1629 5350 200 3128 1948 7601 332 6973 1869 2789 2111 4339 9327 9595 1087 4585 7506 9935 850 6087 1432 4932 723 5863 468 6824 3200 7483 2005 8553 2798 7680 991 8595 95 2379 4704 8773 5388 8503 1316 9928 2164 60...
output:
178476322146618 212581735474540 97664015826725 32720953154164 98586242468815 182463260674934 161421747872055 146457120526990 216189917671016 238821446345616 195878926340178 194435416584804 198022374418219 69770884358102 173557137328055 184789377313284 218050741659725 224873943256047 107596574583740 155161375818218 198962054431430 155083869143706 159732494798964 152901845021079 150497517316486 169486595549179 104305478333524 80464141081432 217733323934787 186360899527210 233320610399317 155792953...
result:
ok 10000 lines