QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#652964#6977. T - Coveringxiay100 ✓179ms51900kbC++143.0kb2024-10-18 19:22:112024-10-18 19:22:20

Judging History

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

  • [2024-10-18 19:22:20]
  • 评测
  • 测评结果:100
  • 用时:179ms
  • 内存:51900kb
  • [2024-10-18 19:22:11]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define INF 1e18
using namespace std;

const int N = 1000000 + 5;
int n, m;
int k;
int vec[N];
int x[N], y[N];
int mp[N];
long long sum[N];
int vis[N], t[N];
int as[N], mn[N];
int fx[12] = {1, 0, -1, 0, 1, 1, -1, -1, -2, 0, 2, 0};
int fy[12] = {0, 1, 0, -1, 1, -1, 1, -1, 0, 2, 0, -2};

int id(int x, int y) {
    return x * m + y;
}

int fa[N], sz[N];
int find(int x) {
    return (x == fa[x] ? x : fa[x] = find(fa[x]));
}
void merge(int x, int y) {
    x = find(x), y = find(y);

    if (x == y) {
        return ;
    }

    fa[x] = y;
    sz[y] += sz[x];
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // cout << id(i, j) << "\n";
            cin >> vec[id(i, j)];
        }
    }

    // cout << n << " "
    cin >> k;
    int ans = 0;

    for (int i = 1; i <= k; i++) {
        cin >> x[i] >> y[i];
        ans += vec[id(x[i], y[i])];
        mp[id(x[i], y[i])] = i;
        fa[i] = i;
        mn[i] = INF;
        sz[i] = 1;

        for (int j = 0; j < 4; j++) {
            int vx = x[i] + fx[j], vy = y[i] + fy[j];

            if (vx < 0 || vy < 0 || vx >= n || vy >= m) {
                continue;
            }

            sum[id(vx, vy)]++;
        }
    }

    for (int i = 1; i <= k; i++) {
        int ux = x[i], uy = y[i];

        for (int j = 0; j < 12; j++) {
            int vx = ux + fx[j], vy = uy + fy[j];

            if (vx < 0 || vy < 0 || vx >= n || vy >= m) {
                continue;
            }

            if (mp[id(vx, vy)]) {
                merge(i, mp[id(vx, vy)]);
            }
        }
    }

    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < 4; j++) {
            int vx = x[i] + fx[j], vy = y[i] + fy[j];

            if (vx < 0 || vy < 0 || vx >= n || vy >= m) {
                continue;
            }

            if (!mp[id(vx, vy)] && !vis[id(vx, vy)]) {
                as[find(i)] += vec[id(vx, vy)];
                t[find(i)]++;
                vis[id(vx, vy)] = 1;

                if (sum[id(vx, vy)] >= 3) {
                    cout << "No\n";
                    return 0;
                }

                // if (sum[id(vx, vy)] == 1) {
                mn[find(i)] = min(mn[find(i)], vec[id(vx, vy)]);
                // }
            }
        }
    }

    for (int i = 1; i <= k; i++) {
        // cout << fa[i] << '\n';
        if (find(i) == i) {
            // cout << t[i] << " " << sz[i] << "\n";
            if (t[i] < 3 * sz[i]) {
                cout << "No\n";
                return 0;
            }

            if (t[i] > 3 * sz[i]) {
                ans += as[i] - mn[i];
            } else {
                ans += as[i];
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 22040kb

input:

100 100
167 462 315 419 197 696 645 918 133 786 747 376 304 896 983 743 425 102 122 91 135 962 588 329 871 479 226 724 711 808 60 681 38 638 985 626 822 306 515 59 232 313 959 940 760 7 938 375 854 186 366 747 52 791 332 788 523 189 256 851 160 109 65 85 173 458 548 380 869 264 899 815 549 35 985 72...

output:

24675

result:

ok single line: '24675'

Test #2:

score: 5
Accepted
time: 3ms
memory: 22204kb

input:

300 100
278 129 755 856 62 291 794 751 419 417 917 362 534 596 516 346 263 997 796 102 929 833 619 808 875 375 314 939 664 940 292 433 573 944 220 951 397 519 744 21 468 866 70 679 850 855 886 754 965 387 738 861 639 474 681 220 101 557 591 157 411 449 34 368 147 156 404 785 765 422 936 471 761 537 ...

output:

114773

result:

ok single line: '114773'

Test #3:

score: 5
Accepted
time: 12ms
memory: 22584kb

input:

200 500
976 680 503 114 752 851 702 41 974 616 992 507 435 8 592 696 813 579 275 416 690 225 223 763 561 775 517 380 959 677 993 81 261 766 672 668 53 558 500 96 884 949 887 481 344 539 925 905 695 586 339 833 874 751 667 904 646 325 482 480 897 247 169 844 353 159 858 885 783 589 529 852 652 290 65...

output:

234396

result:

ok single line: '234396'

Test #4:

score: 5
Accepted
time: 33ms
memory: 32324kb

input:

750 400
953 374 610 571 97 593 307 353 173 922 363 14 300 695 459 63 387 308 313 712 548 155 549 718 574 347 33 916 895 486 844 897 173 819 53 929 593 823 806 362 484 206 598 741 588 890 887 228 619 820 442 796 192 545 385 685 789 563 588 725 545 272 836 407 839 790 669 22 250 699 819 961 43 808 754...

output:

1140468

result:

ok single line: '1140468'

Test #5:

score: 5
Accepted
time: 120ms
memory: 44808kb

input:

1000 1000
69 981 531 651 754 142 361 12 122 466 23 122 917 767 624 992 40 666 978 848 596 510 784 933 551 339 536 219 758 470 55 54 425 604 466 306 365 2 358 802 591 601 835 836 644 808 451 844 858 434 137 945 944 224 991 828 224 25 174 722 375 192 895 512 811 990 436 162 819 622 920 443 986 418 222...

output:

2300651

result:

ok single line: '2300651'

Subtask #2:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 5ms
memory: 22024kb

input:

100 100
888 336 785 617 284 753 186 549 751 523 266 855 685 270 349 442 424 907 79 425 57 345 616 818 656 219 301 665 963 963 541 37 526 185 948 480 331 114 790 635 801 93 482 131 367 252 681 214 729 285 83 904 929 339 375 574 235 31 184 320 91 720 976 957 477 670 485 746 991 603 415 781 145 782 979...

output:

26469

result:

ok single line: '26469'

Test #7:

score: 10
Accepted
time: 3ms
memory: 22232kb

input:

300 100
803 900 143 166 750 465 788 192 578 753 972 580 690 767 806 823 843 920 509 185 410 500 960 399 370 132 879 567 972 356 531 900 315 631 744 653 254 497 58 670 943 427 829 305 473 119 565 322 202 293 805 234 682 446 951 715 884 766 724 541 167 991 380 358 105 249 411 366 497 988 109 827 904 9...

output:

No

result:

ok single line: 'No'

Test #8:

score: 10
Accepted
time: 12ms
memory: 24732kb

input:

200 500
498 492 914 921 265 527 903 220 216 875 410 122 490 770 322 674 133 857 651 660 944 485 277 595 957 701 11 295 652 803 271 132 730 812 426 39 795 536 228 672 269 259 42 326 526 410 476 840 257 972 235 216 20 749 793 598 35 406 891 520 246 433 669 253 905 835 361 347 751 559 818 401 558 364 5...

output:

237051

result:

ok single line: '237051'

Test #9:

score: 10
Accepted
time: 34ms
memory: 32256kb

input:

750 400
762 562 731 673 395 607 988 177 321 375 693 519 720 30 786 941 485 744 946 164 977 359 383 957 8 732 857 882 239 735 506 350 897 372 527 818 434 4 645 597 153 414 226 613 365 844 211 810 193 360 941 2 443 40 910 295 528 300 391 122 257 943 206 48 144 599 677 274 790 889 717 519 121 185 410 1...

output:

1154101

result:

ok single line: '1154101'

Test #10:

score: 10
Accepted
time: 121ms
memory: 46956kb

input:

1000 1000
695 754 153 35 326 201 235 704 553 449 812 67 519 24 22 350 12 5 607 643 752 347 474 32 253 168 310 721 934 173 969 875 410 774 840 932 550 860 738 574 316 57 407 310 219 423 829 177 515 435 566 660 549 972 197 374 214 367 189 651 841 944 814 576 374 967 441 622 115 476 73 499 688 586 790 ...

output:

2299687

result:

ok single line: '2299687'

Subtask #3:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #11:

score: 10
Accepted
time: 4ms
memory: 22044kb

input:

100 100
371 34 403 713 631 105 969 32 919 164 837 177 24 155 41 469 516 618 855 791 200 335 1000 447 174 63 668 935 15 24 54 486 52 72 114 503 643 850 259 699 846 849 829 77 35 173 33 754 288 28 409 169 887 481 298 648 908 386 231 402 577 820 163 227 476 434 198 289 706 909 420 262 463 754 528 576 7...

output:

22126

result:

ok single line: '22126'

Test #12:

score: 10
Accepted
time: 3ms
memory: 24276kb

input:

300 100
29 577 432 536 236 283 710 862 90 751 748 543 565 552 232 434 934 690 787 846 157 375 479 97 273 802 30 33 372 864 173 694 972 595 941 95 445 103 563 304 44 828 931 709 810 565 346 945 652 287 937 956 545 409 79 638 325 629 106 878 316 57 843 925 308 441 205 349 533 907 410 81 838 351 283 84...

output:

109947

result:

ok single line: '109947'

Test #13:

score: 10
Accepted
time: 12ms
memory: 26720kb

input:

200 500
150 403 829 446 899 258 53 922 503 880 317 843 702 16 692 350 842 345 106 808 745 460 115 704 509 422 106 815 621 505 769 860 778 159 639 960 294 643 320 146 989 512 222 464 596 264 469 349 257 943 844 915 757 647 947 178 37 100 730 812 932 570 680 624 319 986 196 731 694 371 825 162 697 368...

output:

232723

result:

ok single line: '232723'

Test #14:

score: 10
Accepted
time: 37ms
memory: 32256kb

input:

750 400
516 626 364 476 555 273 135 163 68 640 20 976 39 233 769 618 536 327 115 53 946 690 978 612 418 817 926 932 783 999 452 766 657 493 16 868 573 636 467 550 706 456 836 530 395 966 564 196 884 724 28 751 894 118 221 924 324 191 564 984 172 309 530 551 231 276 442 93 498 504 343 913 530 575 633...

output:

1173196

result:

ok single line: '1173196'

Test #15:

score: 10
Accepted
time: 120ms
memory: 45024kb

input:

1000 1000
399 478 553 535 408 74 770 825 284 262 752 430 777 2 420 45 435 297 115 835 425 786 912 996 644 128 999 963 649 259 241 369 271 259 898 167 422 996 677 459 718 766 380 425 315 714 713 589 926 527 115 878 982 31 166 785 356 523 338 908 838 209 930 988 799 48 398 403 585 125 110 336 238 690 ...

output:

2281678

result:

ok single line: '2281678'

Subtask #4:

score: 10
Accepted

Test #16:

score: 10
Accepted
time: 3ms
memory: 21944kb

input:

10 100
696 130 360 638 356 42 591 247 998 570 900 233 175 607 166 846 919 90 992 613 334 265 248 912 747 27 992 608 933 641 314 137 336 179 339 972 401 950 414 440 543 946 930 44 61 599 722 644 842 378 970 300 187 698 87 184 194 405 546 487 146 208 112 731 398 139 973 6 45 833 619 586 700 171 255 35...

output:

24252

result:

ok single line: '24252'

Test #17:

score: 10
Accepted
time: 0ms
memory: 22076kb

input:

10 200
447 58 51 962 636 547 773 171 107 390 129 505 582 44 268 284 351 998 78 265 359 174 129 153 267 152 67 35 336 721 374 631 386 616 934 243 43 478 396 989 887 887 885 474 528 900 174 32 836 860 839 651 423 845 876 111 996 349 870 280 425 288 505 103 157 235 235 980 229 985 317 232 921 634 141 7...

output:

120358

result:

ok single line: '120358'

Test #18:

score: 10
Accepted
time: 9ms
memory: 22060kb

input:

10 5000
223 864 106 277 606 703 512 909 511 154 253 68 706 493 138 962 688 664 123 220 616 34 241 310 747 804 199 193 486 508 209 5 588 56 370 141 119 550 514 992 876 815 522 672 803 940 386 642 186 99 616 791 445 937 645 799 562 3 710 595 10 333 158 332 254 63 588 913 459 706 700 944 141 536 808 43...

output:

234206

result:

ok single line: '234206'

Test #19:

score: 10
Accepted
time: 3ms
memory: 22000kb

input:

10 3000
415 546 964 515 24 24 549 363 897 683 561 197 809 267 510 63 228 285 72 73 41 2 115 528 897 874 91 518 685 164 996 868 54 478 921 861 996 872 261 677 369 726 814 431 835 597 382 952 543 585 99 291 700 860 359 333 679 142 591 13 168 521 531 140 284 674 254 256 599 680 547 188 436 387 241 784 ...

output:

1140344

result:

ok single line: '1140344'

Test #20:

score: 10
Accepted
time: 15ms
memory: 24344kb

input:

10 10000
612 600 782 459 386 570 507 844 787 785 394 160 90 74 43 606 440 519 423 465 730 704 994 546 253 615 312 735 661 874 322 19 471 335 844 129 532 664 539 45 626 76 180 72 307 624 732 397 549 927 649 910 455 744 51 774 651 647 189 820 566 48 281 702 763 263 381 280 352 308 291 232 170 730 286 ...

output:

2285306

result:

ok single line: '2285306'

Subtask #5:

score: 15
Accepted

Test #21:

score: 15
Accepted
time: 0ms
memory: 22008kb

input:

7 10
31 432 95 332 888 929 367 537 562 279
232 941 373 351 492 868 896 76 509 103
561 236 741 771 47 965 807 307 292 946
276 335 272 433 359 722 676 447 466 771
239 397 875 658 553 202 285 838 836 722
65 289 748 434 194 485 361 686 660 46
570 976 722 775 466 549 709 907 409 658
10
1 2
1 4
1 6
1 8
3 ...

output:

19890

result:

ok single line: '19890'

Test #22:

score: 15
Accepted
time: 0ms
memory: 22060kb

input:

6 10
45 185 859 703 988 203 881 543 885 604
276 965 940 581 331 860 69 681 94 288
911 796 989 476 143 58 740 523 467 219
46 171 330 228 581 544 584 966 622 329
953 22 784 999 413 840 270 35 511 413
50 74 365 573 875 836 856 314 290 524
7
1 1
2 2
2 5
2 7
3 4
4 7
4 9

output:

No

result:

ok single line: 'No'

Test #23:

score: 15
Accepted
time: 2ms
memory: 21880kb

input:

9 10
856 21 296 228 403 862 260 478 444 251
683 356 125 1000 855 625 612 524 208 233
92 73 479 954 235 541 921 746 363 557
388 273 542 752 954 220 233 887 420 658
148 430 246 668 879 436 115 879 438 202
871 452 995 835 230 166 149 100 757 338
349 448 456 920 602 781 213 988 304 857
19 727 146 474 27...

output:

No

result:

ok single line: 'No'

Test #24:

score: 15
Accepted
time: 0ms
memory: 21948kb

input:

7 8
683 447 196 539 593 238 538 935
298 797 347 993 205 177 630 837
669 551 312 39 355 525 28 392
790 134 786 537 594 612 60 307
937 145 383 912 614 143 453 612
764 821 268 175 546 506 570 381
850 431 547 693 497 538 541 285
9
1 2
1 4
1 6
3 2
3 4
3 6
5 2
5 4
5 6

output:

No

result:

ok single line: 'No'

Test #25:

score: 15
Accepted
time: 0ms
memory: 22008kb

input:

11 10
490 841 895 216 424 798 156 242 702 3
67 903 271 309 24 456 594 558 14 807
629 420 271 100 238 276 688 983 184 648
364 206 591 649 578 243 154 994 895 737
237 186 993 931 964 559 453 126 226 664
989 280 867 905 635 938 983 162 887 868
749 181 353 275 966 971 2 628 370 930
886 550 920 420 256 8...

output:

20599

result:

ok single line: '20599'

Subtask #6:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #26:

score: 20
Accepted
time: 0ms
memory: 22012kb

input:

100 100
28 34 784 392 244 52 495 757 494 195 139 762 230 515 601 605 968 675 603 131 847 478 928 302 681 555 872 623 408 155 893 850 361 816 656 755 216 220 322 537 58 18 354 25 686 187 429 475 242 983 51 91 363 842 748 724 287 389 825 844 484 393 813 138 60 86 841 584 678 718 591 787 747 921 260 14...

output:

141270

result:

ok single line: '141270'

Test #27:

score: 20
Accepted
time: 3ms
memory: 24280kb

input:

300 100
756 676 249 244 875 280 799 676 492 637 416 416 630 457 996 207 743 119 69 156 710 393 704 621 69 622 608 46 390 508 727 497 277 65 331 443 46 792 743 267 79 241 554 266 767 111 191 925 226 431 810 524 882 439 794 417 788 88 613 978 518 650 344 130 528 922 828 59 163 616 617 565 474 928 718 ...

output:

293942

result:

ok single line: '293942'

Test #28:

score: 20
Accepted
time: 11ms
memory: 26916kb

input:

200 500
325 189 354 740 863 290 401 334 804 846 336 21 943 684 989 167 171 6 168 158 788 151 346 502 621 845 657 879 30 78 105 487 900 640 845 449 413 50 273 978 758 339 513 418 131 670 317 334 348 978 270 33 560 444 44 572 390 789 804 935 505 80 801 960 0 206 590 273 244 680 820 565 39 887 753 153 ...

output:

573271

result:

ok single line: '573271'

Test #29:

score: 20
Accepted
time: 40ms
memory: 30284kb

input:

750 400
449 540 73 985 232 195 559 271 514 916 482 707 225 507 735 427 432 197 900 358 210 471 135 198 446 808 747 836 320 741 424 914 724 87 981 331 409 459 452 932 858 559 126 962 52 638 66 36 909 774 578 432 55 947 543 668 142 319 961 829 757 20 671 100 243 697 932 492 82 253 675 82 594 876 197 1...

output:

1156197

result:

ok single line: '1156197'

Test #30:

score: 20
Accepted
time: 117ms
memory: 47040kb

input:

1000 1000
710 228 670 631 742 156 940 444 305 781 981 196 541 786 965 683 804 834 988 354 112 263 752 632 253 802 834 392 371 860 741 47 958 994 994 758 258 794 325 954 177 469 698 492 385 161 594 349 133 890 359 85 963 320 660 245 88 523 439 44 774 590 297 719 163 207 29 329 825 824 295 932 948 1 3...

output:

2301409

result:

ok single line: '2301409'

Subtask #7:

score: 30
Accepted

Dependency #6:

100%
Accepted

Test #31:

score: 30
Accepted
time: 179ms
memory: 51900kb

input:

19 49999
509 0 409 971 820 633 260 325 351 246 584 248 759 678 752 968 21 385 53 714 98 76 878 966 98 836 154 879 367 668 295 685 699 796 328 506 187 697 710 831 240 714 792 138 546 144 47 688 73 998 994 115 732 418 357 343 166 48 214 655 864 942 654 480 417 656 819 422 92 878 629 609 415 302 620 48...

output:

299770997

result:

ok single line: '299770997'

Test #32:

score: 30
Accepted
time: 118ms
memory: 43476kb

input:

199 4999
649 937 717 203 306 643 51 774 276 977 628 503 612 418 182 552 259 413 717 900 649 198 997 209 286 480 582 550 85 608 677 325 24 238 144 283 652 133 670 595 362 571 137 830 162 308 700 928 173 815 691 996 471 409 668 923 710 313 462 763 956 713 284 10 643 483 637 308 589 399 617 505 326 380...

output:

No

result:

ok single line: 'No'

Test #33:

score: 30
Accepted
time: 128ms
memory: 48332kb

input:

19999 49
679 855 816 532 490 797 610 695 538 107 810 865 903 706 549 987 149 805 909 815 518 192 12 364 447 629 783 569 93 316 633 116 757 875 30 991 512 311 200 229 585 660 629 293 649 419 527 575 724
599 870 661 734 645 346 31 312 271 40 943 28 441 790 886 402 539 858 107 936 704 502 676 214 103 3...

output:

19991026

result:

ok single line: '19991026'

Test #34:

score: 30
Accepted
time: 124ms
memory: 41796kb

input:

199 4999
452 166 818 554 872 764 356 366 796 468 850 891 571 236 389 195 455 578 133 852 335 469 162 371 655 123 907 926 975 497 763 247 672 178 850 558 103 470 254 625 289 833 4 696 962 195 212 106 636 257 586 336 656 366 897 319 935 418 151 358 215 619 632 441 700 964 167 376 380 845 587 683 642 3...

output:

10368071

result:

ok single line: '10368071'

Test #35:

score: 30
Accepted
time: 149ms
memory: 48788kb

input:

999 999
844 440 226 561 212 649 563 746 783 502 604 27 136 139 623 978 761 981 927 969 398 349 568 234 202 216 343 574 438 235 594 358 618 709 149 128 10 386 286 177 590 340 498 16 702 345 85 565 303 505 933 915 753 924 65 894 386 84 875 609 483 647 955 906 662 634 849 553 146 978 147 409 585 544 60...

output:

100520160

result:

ok single line: '100520160'