QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#8628#1062. 世界地图Qingyu100 ✓694ms67348kbC++204.2kb2021-04-03 11:27:532021-12-19 10:39:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 10:39:45]
  • 评测
  • 测评结果:100
  • 用时:694ms
  • 内存:67348kb
  • [2021-04-03 11:27:53]
  • 提交

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