QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#168788 | #6639. Disk Tree | ucup-team1209 | WA | 423ms | 35176kb | C++20 | 2.0kb | 2023-09-08 22:00:33 | 2023-09-08 22:00:34 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 200005;
using db = double;
using cp = std::complex<db>;
const db pi = std::acos(-1);
std::mt19937 gen(time(0) + (size_t) new char);
int n;
cp a[N], b[N];
int r[N], id0[N], id1[N];
int pos[N];
struct edge { int u, v; db w; };
std::vector<edge> e;
int anc[N];
db dist(int x, int y) { return abs(a[x] - a[y]) - r[x] - r[y]; }
struct pr {
db w; int id;
} bit[N];
int find(int x) {
return anc[x] == x ? x : anc[x] = find(anc[x]);
}
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for(int i = 0;i < n;++i) {
int x, y; cin >> x >> y >> r[i];
a[i] = cp(x, y);
id0[i] = i;
id1[i] = i;
anc[i] = i;
}
for(db arg : {0., 0.25, 0.5, 0.75}) {
cp r = std::polar(1., arg * pi * 2);
for(int i = 0;i < n;++i) b[i] = a[i] * r;
std::sort(id0, id0 + n, [](int x, int y) { return b[x].real() < b[y].real(); });
std::sort(id1, id1 + n, [](int x, int y) { return b[x].imag() < b[y].imag(); });
for(int j = 0;j < n;++j) {
pos[id1[j]] = j + 1;
}
for(int i = 1;i <= n;++i) {
bit[i] = {5e9, -1};
}
for(int i = n - 1;i >= 0;--i) {
int x = id0[i];
int id = -1;
db dx = 5e9;
for(int i = pos[x];i <= n;i += i & -i) {
int t = bit[i].id;
if(t != -1) {
db dd = dist(t, x);
if(id == -1) {
id = t;
dx = dd;
} else {
if(dd < dx) {
dx = dd;
id = t;
}
}
}
}
pr z = { b[x].real() + b[x].imag() - ::r[x], x};
for(int i = pos[x];i;i &= i - 1) {
if(z.w < bit[i].w) bit[i] = z;
}
if(id >= 0) {
e.push_back({x, id, dx});
}
}
}
sort(e.begin(), e.end(), [](edge x, edge y) { return x.w < y.w; });
cout << "YES" << '\n';
for(auto [u, v, w] : e) {
if(find(u) != find(v)) {
cout << (int) a[u].real() << ' ' << (int) a[u].imag() << ' ';
cout << (int) a[v].real() << ' ' << (int) a[v].imag() << '\n';
anc[find(u)] = find(v);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10048kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 5 1 0 0 5 10 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 3ms
memory: 12192kb
input:
2 1 1 1 3 3 1
output:
YES 1 1 3 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 3ms
memory: 10144kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 3 20 10 10 2 0 10 10 10 10 20 20 10 10 20 0
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 12228kb
input:
10 29 29 2 28 55 10 99 81 4 17 82 10 45 88 10 48 68 10 0 8 10 98 95 10 34 0 10 17 24 10
output:
YES 99 81 98 95 48 68 45 88 17 24 29 29 0 8 17 24 28 55 48 68 17 82 45 88 34 0 17 24 28 55 17 24 98 95 45 88
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 1ms
memory: 12212kb
input:
100 490 783 12 666 460 55 561 245 6 223 323 25 3 520 77 225 161 24 514 190 16 997 914 100 412 265 100 374 610 36 296 854 39 601 901 2 307 21 100 390 422 24 940 414 32 332 438 35 553 992 100 235 775 3 656 901 37 770 417 22 649 305 100 448 84 3 375 939 77 910 847 9 776 357 37 743 97 100 371 502 39 508...
output:
YES 649 305 560 422 375 939 468 868 743 97 742 210 92 366 204 512 447 40 448 84 307 21 205 100 964 284 837 286 811 693 809 794 375 939 293 965 981 11 865 52 375 939 296 854 304 613 374 610 160 703 252 629 445 639 563 635 964 284 899 204 160 703 119 603 508 524 458 464 116 850 67 952 95 208 76 226 13...
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 1ms
memory: 12264kb
input:
200 2948 9798 687 3897 647 35 3918 587 28 1262 2717 206 1315 9524 20 2381 305 1000 4344 6858 20 6234 8949 53 5168 4772 85 5044 6109 158 72 7670 132 7300 1213 837 5427 2263 1000 1785 3009 276 6136 1421 43 1629 5620 29 6445 9489 242 8443 3141 1000 4118 4307 63 1874 5238 291 1964 5785 73 7794 3934 18 3...
output:
YES 4160 6939 3841 6121 1828 4099 1566 4450 5710 4771 5901 4668 6334 1443 7300 1213 4278 321 4775 842 4160 6939 4344 6858 4718 3379 4284 3385 9940 2103 9446 2407 8040 7929 7634 8387 8914 1613 8591 1690 2381 305 2395 2085 9671 1058 8844 424 8914 1613 8844 424 63 2852 147 1148 7502 5454 6908 4386 6837...
result:
ok answer = 1
Test #7:
score: 0
Accepted
time: 3ms
memory: 12292kb
input:
300 42942 37079 222 49441 21821 1695 61023 31153 561 86630 26307 352 36940 78253 213 7841 81086 626 47425 22290 374 17694 68695 648 38259 64794 998 43599 46942 9662 9204 2816 1965 38652 83568 4057 4046 29001 1034 72591 63214 587 75984 64859 1112 70005 72177 576 34522 52126 652 56627 48785 1747 78820...
output:
YES 59944 148 59945 7276 26217 53454 15549 49146 27055 9398 30743 15955 54156 44092 54720 46175 42729 76361 46373 81005 49555 87747 48642 86091 48642 86091 49759 86207 74594 17647 77261 898 90608 87653 83657 87664 84773 93522 90608 87653 908 79893 11003 92828 62892 19999 74594 17647 44439 62520 4786...
result:
ok answer = 1
Test #8:
score: 0
Accepted
time: 3ms
memory: 12200kb
input:
1000 558504245 246224785 100000000 971981730 913036757 1821458 198791767 482624549 5998171 540520619 353988177 8924682 183178222 46223569 9859905 118485076 22129062 7497235 274928891 417171180 372954 230079763 468235825 289869 859092765 562864738 5551376 129036518 743777318 3969979 265158223 3092933...
output:
YES 969959032 159770753 935651301 194859808 407855873 545059764 387522770 540197621 709709305 895610707 803699647 926616709 957410466 524462618 951999910 625259461 805699634 244675073 842117276 266665723 21557591 472068545 9506894 429721563 703832774 417735074 606567077 439287468 944920611 405541788...
result:
ok answer = 1
Test #9:
score: 0
Accepted
time: 7ms
memory: 12380kb
input:
3000 442876143 334276354 3627270 526253918 947313397 2498956 566692880 229330019 4243066 497859604 658736917 13012787 315969653 65582717 1400013 394215653 932651144 1655676 58249045 973232518 860150 860773683 959388251 1594726 23803673 921365885 5926749 730359196 818999592 1521282 971839312 22835235...
output:
YES 290472947 49435962 281268489 57797275 338210244 314788266 336396685 305520991 504627632 484355357 511679958 472770476 385991211 898942427 381063725 888883942 109415638 638809020 106386194 648286633 443740179 557407886 445317829 548859629 278141533 211881820 287619836 198910855 43444734 915079984...
result:
ok answer = 1
Test #10:
score: 0
Accepted
time: 7ms
memory: 10296kb
input:
7000 601805179 978984160 464352 918208048 607538668 2214109 328147216 806677103 3901695 961794394 719893281 1114470 453816635 992288784 274949 778724702 692479905 1170018 169287513 886715521 576156 812072299 118324465 93778 726229729 150105801 3593039 368683874 642143790 1277375 40087476 151799345 4...
output:
YES 952741689 195407765 948962033 192473096 335978465 621454749 302136515 662205213 181702051 225543777 191910423 222317550 108639664 832228566 112166501 828136227 360578188 879715637 367657522 874112964 395639996 56994662 409421203 1671512 115667148 196841066 113675287 272880588 660724674 691603733...
result:
ok answer = 1
Test #11:
score: 0
Accepted
time: 8ms
memory: 12868kb
input:
10000 645 4710 5 1554 4072 7 6505 2760 1 6125 8212 11 9802 9537 3 6584 4356 6 1104 6649 23 4580 2623 20 3107 2460 1 4689 1662 2 7815 161 14 8718 3658 28 2900 63 15 1741 7296 44 8380 4608 50 2212 8514 4 7919 3069 17 1638 6057 3 504 9867 18 7869 8021 14 866 9239 5 3452 8042 4 9049 7222 4 4447 1004 5 9...
output:
YES 9942 7773 9941 6761 8379 5377 8980 5036 1806 9435 1140 9308 3934 629 3270 702 2042 8866 1806 9435 54 4255 588 4254 1697 6744 1698 6223 2832 3345 3511 4090 7500 3958 7950 3959 7062 3959 7500 3958 7501 4394 7500 3958 5549 7629 5924 7630 8576 4074 8575 4441 8362 3787 8576 4074 6477 9628 6424 9977 4...
result:
ok answer = 1
Test #12:
score: 0
Accepted
time: 198ms
memory: 25516kb
input:
100000 956095525 596102106 2 461544095 587257542 118 884402350 357055086 14228 547768407 186052059 263162 827807425 303694996 474924 692537425 44608243 131609 504660936 451030143 15134 207539367 899608364 20283 919236289 724317925 6 386476373 727023405 323 781914406 792770865 1064 411548762 2476126 ...
output:
YES 892145544 423239295 892696561 422861520 737182558 31629185 737205369 31606130 791386989 34057684 790259785 35554795 575900390 197298321 576712653 196103190 871840112 672618377 871778107 671901046 971859066 699788760 972388111 699494151 607697634 947278085 606473337 946634089 267828294 606295817 ...
result:
ok answer = 1
Test #13:
score: 0
Accepted
time: 397ms
memory: 34028kb
input:
200000 267774456 105702394 770 297991198 776424841 124 703700092 120262616 341808 212663821 221756923 367 195031049 705083745 66 692227605 63745620 1221 615879799 481139131 3053 93198187 239262367 141042 645539116 89213985 1679 312339485 547897747 2701 546940040 418847605 2 100457345 231142218 2 290...
output:
YES 73480409 112707894 75807544 112300029 974169585 619209298 976452843 619556934 732071653 615357564 730568325 616291877 182294625 509124843 180791485 507855412 902284179 882065660 902126642 881325390 420643702 241791571 420658973 241541045 70202096 599247436 70259530 599116568 870390405 306105841 ...
result:
ok answer = 1
Test #14:
score: 0
Accepted
time: 407ms
memory: 34948kb
input:
200000 890760596 387635202 407021 845949678 865384827 250 298937825 444813049 30 257079208 603496538 24935 825947861 514433442 276 664047255 283065064 651111 481691537 759981944 616 953630211 233077236 207 716089940 174481709 876827 807394429 737990862 50258 9195111 176890156 946 209723712 839382384...
output:
YES 701175461 366336859 700926819 363782478 258911614 139798076 259664312 140583575 571382827 413589615 572864108 412884598 59137802 682714019 59157956 682658775 890443024 926016890 892414809 926001644 632442573 782295890 631227659 780874910 917748361 850287970 917708835 849128591 392781170 94486009...
result:
ok answer = 1
Test #15:
score: 0
Accepted
time: 423ms
memory: 33760kb
input:
200000 21940906 14228149 878 947616612 637746482 278 490310177 117451293 1714712 278642428 651582650 1 214397046 727562852 3 314365021 93147008 158746 367463298 30253119 650745 816993648 678947261 4384 503557517 182822048 1116 61881753 989787068 109052 632366340 971129473 26 870552310 805607887 5436...
output:
YES 651143559 352449533 651139377 352466867 569112950 674044827 568354398 675585065 429430280 411122054 430172210 411030216 326952582 782461575 326919810 781590564 631594179 32612462 631053962 32398092 467468968 127421520 467251791 126240740 192143717 610724525 191720861 609273318 312918516 94606999...
result:
ok answer = 1
Test #16:
score: -100
Wrong Answer
time: 409ms
memory: 35176kb
input:
200000 81117 91365 1 68731 21152 3 37456 24002 2 37581 56006 3 52472 65837 1 68592 30967 2 37017 58189 11 21553 64504 95 94147 72332 80 82905 892 21 37593 40659 5 83451 10026 2 24925 11872 13 84418 48948 156 52378 43742 51 27379 10720 162 37042 54394 1 92324 20573 1 69506 96945 133 87826 40634 3 962...
output:
YES 23430 54471 23525 54295 77122 74437 76931 74403 56282 3687 56476 3688 82844 85747 82675 85836 6389 98610 6577 98611 39514 66149 39401 66000 82103 20535 82270 20536 5740 32096 5669 32227 49411 67798 49347 67669 26410 82691 26496 82804 64656 98254 64797 98255 734 69863 874 69862 9187 80898 9159 80...
result:
wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks