QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#784879 | #4952. Cutting with Lasers | Yarema# | AC ✓ | 16ms | 20428kb | C++20 | 1.6kb | 2024-11-26 16:13:25 | 2024-11-26 16:13:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;
struct DSU
{
int n;
VI p, sz;
DSU(int _n = 0)
{
n = _n;
p.resize(n);
iota(ALL(p), 0);
sz.assign(n, 1);
}
int find(int v)
{
if (v == p[v])
return v;
return p[v] = find(p[v]);
}
bool unite(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
return false;
if (sz[u] > sz[v])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
return true;
}
};
const int N = 1047;
int r[N][N];
int c[N][N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int x, y;
cin >> x >> y;
x++, y++;
FOR (it, 0, n)
{
int x2, y2;
cin >> x2 >> y2;
x2++, y2++;
if (x == x2)
{
FOR (i, min(y, y2), max(y, y2))
c[i][x] = 1;
}
else
{
FOR (i, min(x, x2), max(x, x2))
r[y][i] = 1;
}
x = x2;
y = y2;
}
DSU d(N * N);
FOR (i, 1, N)
{
FOR (j, 1, N)
{
int f1 = i * N + j;
if (!c[i][j])
d.unite(f1, i * N + j - 1);
if (!r[i][j])
d.unite(f1, i * N + j - N);
}
}
int ans = 0;
FOR (i, 1, N)
{
FOR (j, 1, N)
if (d.find(i * N + j) != d.find(1))
ans = max(ans, d.sz[d.find(i * N + j)]);
}
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 15ms
memory: 14004kb
input:
8 2 1 7 1 7 4 3 4 3 2 5 2 5 6 2 6 2 1
output:
17
result:
ok single line: '17'
Test #2:
score: 0
Accepted
time: 14ms
memory: 13992kb
input:
14 1 1 8 1 8 6 6 6 6 2 2 2 2 4 7 4 7 5 3 5 3 3 4 3 4 6 1 6 1 1
output:
21
result:
ok single line: '21'
Test #3:
score: 0
Accepted
time: 11ms
memory: 16448kb
input:
4 1 1 1 1000 1000 1000 1000 1 1 1
output:
998001
result:
ok single line: '998001'
Test #4:
score: 0
Accepted
time: 11ms
memory: 13828kb
input:
4 1 1 1 2 2 2 2 1 1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 12ms
memory: 19636kb
input:
6 1000 1000 1000 500 1 500 1 1 500 1 500 1000 1000 1000
output:
250000
result:
ok single line: '250000'
Test #6:
score: 0
Accepted
time: 15ms
memory: 18924kb
input:
12 530 101 530 89 636 89 636 52 180 52 180 906 236 906 236 910 828 910 828 423 69 423 530 423 530 101
output:
315352
result:
ok single line: '315352'
Test #7:
score: 0
Accepted
time: 12ms
memory: 18996kb
input:
18 474 189 474 32 477 32 477 359 715 359 715 698 935 698 935 447 939 447 939 984 1000 984 1000 988 305 988 305 992 590 992 590 31 660 31 660 189 474 189
output:
144833
result:
ok single line: '144833'
Test #8:
score: 0
Accepted
time: 7ms
memory: 18896kb
input:
16 459 407 807 407 807 187 892 187 892 229 946 229 946 219 275 219 275 187 558 187 558 622 956 622 956 65 998 65 998 40 459 40 459 407
output:
197167
result:
ok single line: '197167'
Test #9:
score: 0
Accepted
time: 15ms
memory: 18024kb
input:
12 281 573 281 971 156 971 156 988 897 988 897 997 989 997 989 998 312 998 312 601 74 601 74 573 281 573
output:
14122
result:
ok single line: '14122'
Test #10:
score: 0
Accepted
time: 15ms
memory: 18624kb
input:
46 489 450 489 205 322 205 322 178 306 178 306 415 291 415 291 886 80 886 80 741 43 741 43 479 36 479 36 287 32 287 32 752 681 752 681 592 788 592 788 32 23 32 23 4 17 4 17 641 532 641 532 525 301 525 301 380 632 380 632 139 118 139 118 298 747 298 747 185 818 185 818 425 181 425 181 333 960 333 960...
output:
149424
result:
ok single line: '149424'
Test #11:
score: 0
Accepted
time: 12ms
memory: 18828kb
input:
36 526 139 213 139 213 118 101 118 101 31 49 31 49 725 33 725 33 147 18 147 18 136 229 136 229 154 174 154 174 116 65 116 65 94 42 94 42 79 337 79 337 53 239 53 239 46 201 46 201 40 88 40 88 19 313 19 313 12 409 12 409 11 523 11 523 938 902 938 902 766 902 139 526 139
output:
302821
result:
ok single line: '302821'
Test #12:
score: 0
Accepted
time: 12ms
memory: 19756kb
input:
38 776 919 776 464 699 464 699 405 971 405 971 748 981 748 981 985 1000 985 1000 996 223 996 223 999 198 999 198 798 87 798 87 361 52 361 52 322 186 322 186 678 132 678 132 566 2 566 2 125 252 125 252 684 690 684 690 456 678 456 678 47 389 47 389 7 918 7 918 990 559 990 559 991 637 991 637 919 776 919
output:
443276
result:
ok single line: '443276'
Test #13:
score: 0
Accepted
time: 12ms
memory: 20120kb
input:
44 149 120 54 120 54 711 428 711 428 484 322 484 322 535 444 535 444 343 64 343 64 180 13 180 13 207 6 207 6 831 928 831 928 341 968 341 968 777 989 777 989 576 561 576 561 788 963 788 963 464 987 464 987 243 661 243 661 975 99 975 99 998 179 998 179 1000 73 1000 73 530 801 530 801 38 961 38 961 712...
output:
273757
result:
ok single line: '273757'
Test #14:
score: 0
Accepted
time: 12ms
memory: 20352kb
input:
42 675 26 675 16 795 16 795 182 617 182 617 40 451 40 451 9 237 9 237 8 132 8 132 980 693 980 693 987 981 987 981 303 15 303 15 35 64 35 64 29 12 29 12 13 557 13 557 925 772 925 772 871 854 871 854 922 840 922 840 974 890 974 890 724 362 724 362 915 74 915 74 771 85 771 85 586 39 586 39 873 438 873 ...
output:
277613
result:
ok single line: '277613'
Test #15:
score: 0
Accepted
time: 15ms
memory: 18656kb
input:
180 36 745 946 745 946 895 953 895 953 389 203 389 203 605 644 605 644 350 66 350 66 89 39 89 39 937 726 937 726 256 869 256 869 3 895 3 895 1 870 1 870 526 999 526 999 17 62 17 62 2 469 2 469 1 786 1 786 704 168 704 168 917 55 917 55 417 29 417 29 296 375 296 375 853 169 853 169 916 782 916 782 618...
output:
68117
result:
ok single line: '68117'
Test #16:
score: 0
Accepted
time: 12ms
memory: 19396kb
input:
118 417 598 128 598 128 43 358 43 358 35 966 35 966 914 204 914 204 991 801 991 801 996 863 996 863 959 519 959 519 125 880 125 880 135 807 135 807 234 653 234 653 825 212 825 212 891 10 891 10 925 776 925 776 873 76 873 76 807 354 807 354 688 307 688 307 903 616 903 616 934 864 934 864 990 802 990 ...
output:
72932
result:
ok single line: '72932'
Test #17:
score: 0
Accepted
time: 12ms
memory: 20428kb
input:
184 815 664 630 664 630 392 161 392 161 556 115 556 115 888 67 888 67 454 178 454 178 47 156 47 156 35 166 35 166 800 71 800 71 166 24 166 24 63 6 63 6 522 560 522 560 987 837 987 837 459 882 459 882 324 489 324 489 565 430 565 430 538 621 538 621 295 418 295 418 402 573 402 573 191 294 191 294 649 ...
output:
35586
result:
ok single line: '35586'
Test #18:
score: 0
Accepted
time: 12ms
memory: 18508kb
input:
102 413 810 908 810 908 593 765 593 765 384 381 384 381 12 285 12 285 114 43 114 43 21 3 21 3 311 798 311 798 552 364 552 364 623 821 623 821 938 864 938 864 913 974 913 974 964 366 964 366 970 605 970 605 999 490 999 490 706 129 706 129 598 565 598 565 451 67 451 67 578 961 578 961 964 574 964 574 ...
output:
52627
result:
ok single line: '52627'
Test #19:
score: 0
Accepted
time: 8ms
memory: 19176kb
input:
300 472 994 472 455 598 455 598 48 13 48 13 685 11 685 11 305 6 305 6 384 2 384 2 117 847 117 847 296 1000 296 1000 288 671 288 671 152 902 152 902 43 965 43 965 20 999 20 999 8 1000 8 1000 778 676 778 676 823 290 823 290 455 14 455 14 631 797 631 797 110 860 110 860 278 964 278 964 187 980 187 980 ...
output:
19731
result:
ok single line: '19731'
Test #20:
score: 0
Accepted
time: 12ms
memory: 19876kb
input:
436 563 513 563 696 926 696 926 359 956 359 956 785 525 785 525 861 937 861 937 565 899 565 899 980 33 980 33 358 270 358 270 660 46 660 46 964 751 964 751 665 572 665 572 231 83 231 83 241 28 241 28 41 22 41 22 937 3 937 3 997 2 997 2 999 1 999 1 634 506 634 506 891 67 891 67 751 55 751 55 51 48 51...
output:
16698
result:
ok single line: '16698'
Test #21:
score: 0
Accepted
time: 16ms
memory: 20184kb
input:
298 616 405 187 405 187 563 864 563 864 120 833 120 833 44 41 44 41 8 369 8 369 6 236 6 236 2 148 2 148 1 96 1 96 857 23 857 23 338 21 338 21 11 12 11 12 445 495 445 495 115 577 115 577 34 831 34 831 300 453 300 453 549 621 549 621 577 533 577 533 538 969 538 969 404 953 404 953 715 961 715 961 350 ...
output:
23726
result:
ok single line: '23726'
Test #22:
score: 0
Accepted
time: 16ms
memory: 18928kb
input:
362 587 6 587 4 287 4 287 718 69 718 69 401 20 401 20 177 60 177 60 576 704 576 704 605 862 605 862 714 903 714 903 809 353 809 353 294 785 294 785 60 542 60 542 802 274 802 274 979 242 979 242 1000 165 1000 165 971 770 971 770 991 334 991 334 998 667 998 667 1000 363 1000 363 767 201 767 201 436 14...
output:
17195
result:
ok single line: '17195'
Test #23:
score: 0
Accepted
time: 10ms
memory: 19968kb
input:
624 544 742 11 742 11 292 6 292 6 951 350 951 350 986 739 986 739 990 953 990 953 962 749 962 749 984 838 984 838 994 937 994 937 289 941 289 941 646 963 646 963 171 986 171 986 8 990 8 990 3 993 3 993 687 285 687 285 604 757 604 757 807 433 807 433 974 599 974 599 986 787 986 787 998 938 998 938 24...
output:
12926
result:
ok single line: '12926'
Test #24:
score: 0
Accepted
time: 11ms
memory: 19984kb
input:
602 45 466 45 927 994 927 994 413 999 413 999 577 193 577 193 543 430 543 430 737 373 737 373 487 456 487 456 412 763 412 763 72 991 72 991 13 997 13 997 238 501 238 501 130 176 130 176 171 586 171 586 271 136 271 136 731 216 731 216 914 211 914 211 958 26 958 26 961 291 961 291 180 739 180 739 74 2...
output:
5689
result:
ok single line: '5689'
Test #25:
score: 0
Accepted
time: 14ms
memory: 19572kb
input:
740 585 8 912 8 912 766 943 766 943 806 737 806 737 893 445 893 445 485 829 485 829 753 988 753 988 982 1000 982 1000 998 849 998 849 467 946 467 946 618 270 618 270 630 720 630 720 637 169 637 169 475 140 475 140 788 68 788 68 988 450 988 450 177 37 177 37 57 324 57 324 459 610 459 610 324 651 324 ...
output:
3280
result:
ok single line: '3280'
Test #26:
score: 0
Accepted
time: 7ms
memory: 19888kb
input:
1798 306 326 396 326 396 942 700 942 700 951 785 951 785 996 467 996 467 1000 396 1000 396 764 85 764 85 681 223 681 223 54 809 54 809 43 719 43 719 26 970 26 970 10 163 10 163 3 975 3 975 887 371 887 371 964 763 964 763 329 890 329 890 10 641 10 641 67 42 67 42 43 184 43 184 903 988 903 988 567 999...
output:
1786
result:
ok single line: '1786'
Test #27:
score: 0
Accepted
time: 8ms
memory: 20064kb
input:
1948 311 112 311 962 883 962 883 148 357 148 357 971 226 971 226 410 107 410 107 789 140 789 140 994 269 994 269 632 147 632 147 724 63 724 63 925 649 925 649 34 200 34 200 387 651 387 651 367 849 367 849 1000 895 1000 895 506 193 506 193 885 368 885 368 354 11 354 11 262 876 262 876 249 1000 249 10...
output:
676
result:
ok single line: '676'
Test #28:
score: 0
Accepted
time: 11ms
memory: 20280kb
input:
4854 246 588 42 588 42 382 98 382 98 233 998 233 998 173 954 173 954 418 971 418 971 551 922 551 922 717 577 717 577 656 506 656 506 648 197 648 197 928 521 928 521 120 889 120 889 109 923 109 923 87 122 87 122 551 736 551 736 691 686 691 686 820 731 820 731 875 990 875 990 49 996 49 996 265 999 265...
output:
180
result:
ok single line: '180'
Test #29:
score: 0
Accepted
time: 16ms
memory: 20140kb
input:
9632 517 210 517 666 66 666 66 606 19 606 19 335 503 335 503 398 1000 398 1000 264 520 264 520 214 348 214 348 119 978 119 978 131 920 131 920 23 490 23 490 18 199 18 199 13 72 13 72 2 11 2 11 881 451 881 451 109 741 109 741 592 205 592 205 75 93 75 93 37 16 37 16 698 12 698 12 7 810 7 810 3 829 3 8...
output:
66
result:
ok single line: '66'