QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#523724 | #1142. Fountain Parks | green_gold_dog# | 5 | 470ms | 49472kb | C++20 | 3.9kb | 2024-08-18 16:58:46 | 2024-08-18 16:58:46 |
Judging History
answer
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct DSU {
vector<ll> p;
DSU(ll n) {
p.resize(n);
for (ll i = 0; i < n; i++) {
p[i] = i;
}
}
ll get(ll a) {
return (p[a] == a ? a : p[a] = get(p[a]));
}
void unite(ll a, ll b) {
p[get(a)] = get(b);
}
};
ll construct_roads(vector<ll> x, vector<ll> y) {
ll n = x.size();
map<pair<ll, ll>, ll> all;
for (ll i = 0; i < n; i++) {
all[make_pair(x[i], y[i])] = i;
}
vector<vector<ll>> to(n);
vector<ll> m1;
for (ll i = 0; i < n; i++) {
if (all.find(make_pair(x[i] + 2, y[i])) != all.end()) {
if (x[i] == 2) {
if (all.find(make_pair(x[i], y[i] - 2)) == all.end()) {
to[i].push_back(all[make_pair(x[i] + 2, y[i])]);
}
} else {
if (all.find(make_pair(x[i] + 2, y[i] - 2)) == all.end()) {
to[i].push_back(all[make_pair(x[i] + 2, y[i])]);
}
}
}
if (all.find(make_pair(x[i], y[i] + 2)) != all.end()) {
to[i].push_back(all[make_pair(x[i], y[i] + 2)]);
}
if (all.find(make_pair(x[i] - 2, y[i])) != all.end()) {
if (x[i] == 4) {
if (all.find(make_pair(x[i] - 2, y[i] - 2)) == all.end()) {
to[i].push_back(all[make_pair(x[i] - 2, y[i])]);
}
} else {
if (all.find(make_pair(x[i], y[i] - 2)) == all.end()) {
to[i].push_back(all[make_pair(x[i] - 2, y[i])]);
}
}
}
if (all.find(make_pair(x[i], y[i] - 2)) != all.end()) {
to[i].push_back(all[make_pair(x[i], y[i] - 2)]);
}
}
set<pair<ll, ll>> have;
vector<ll> u, v, a, b;
DSU d(n);
for (ll i = 0; i < n; i++) {
for (auto j : to[i]) {
d.unite(i, j);
if (have.find(make_pair(j, i)) != have.end() || have.find(make_pair(i, j)) != have.end()) {
continue;
}
u.push_back(i);
v.push_back(j);
have.emplace(i, j);
ll bx = (x[i] + x[j]) / 2, by = (y[i] + y[j]) / 2;
ll add = 1;
if ((x[i] + y[i]) % 4 == 0) {
add = -add;
}
if (x[i] == x[j]) {
add = -add;
if (y[i] < y[j]) {
add = -add;
}
if (x[i] == 2) {
add = -1;
}
if (x[i] == 6) {
add = 1;
}
bx += add;
} else {
if (x[i] < x[j]) {
add = -add;
}
by += add;
}
a.push_back(bx);
b.push_back(by);
}
}
set<ll> aa;
for (ll i = 0; i < n; i++) {
aa.insert(d.get(i));
}
if (aa.size() > 1) {
return 0;
}
build(u, v, a, b);
return 1;
}
#ifdef LOCAL
static void check(bool cond, string message) {
if (!cond) {
printf("%s\n", message.c_str());
fclose(stdout);
exit(0);
}
}
static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
check(!build_called, "build is called more than once");
build_called = true;
m = u.size();
check(int(v.size()) == m, "u.size() != v.size()");
check(int(a.size()) == m, "u.size() != a.size()");
check(int(b.size()) == m, "u.size() != b.size()");
_u = u;
_v = v;
_a = a;
_b = b;
}
int main() {
assert(scanf("%d", &n) == 1);
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
build_called = false;
const int possible = construct_roads(x, y);
check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
if (possible == 1) {
check(build_called, "construct_roads() returned 1 without calling build()");
} else {
check(!build_called, "construct_roads() called build() but returned 0");
}
printf("%d\n", possible);
if (possible == 1) {
printf("%d\n", m);
for (int j = 0; j < m; j++) {
printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
}
}
fclose(stdout);
return 0;
}
#endif
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3804kb
input:
ba73dbf9c7d5e5202834d6a500541c 1 2 2
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 0
result:
ok
Test #2:
score: 5
Accepted
time: 0ms
memory: 3852kb
input:
ba73dbf9c7d5e5202834d6a500541c 2 2 2 2 4
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 1 0 1 1 3
result:
ok
Test #3:
score: 5
Accepted
time: 0ms
memory: 3812kb
input:
ba73dbf9c7d5e5202834d6a500541c 2 2 2 2 6
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #4:
score: 5
Accepted
time: 0ms
memory: 3732kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 2 2 2 4 2 6
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 2 0 1 1 3 1 2 1 5
result:
ok
Test #5:
score: 5
Accepted
time: 0ms
memory: 4084kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 2 2 2 4 2 6 2 8
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 3 0 1 1 3 1 2 1 5 2 3 1 7
result:
ok
Test #6:
score: 5
Accepted
time: 0ms
memory: 4036kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 2 2 2 4 2 8
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #7:
score: 5
Accepted
time: 0ms
memory: 3812kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 2 2 2 4 2 8 2 10
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #8:
score: 5
Accepted
time: 0ms
memory: 4080kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 2 2 2 4 2 6 2 10
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #9:
score: 5
Accepted
time: 176ms
memory: 26168kb
input:
ba73dbf9c7d5e5202834d6a500541c 100000 2 15660 2 23918 2 132200 2 117654 2 162750 2 183010 2 75554 2 29740 2 185476 2 135138 2 194024 2 182274 2 1338 2 42922 2 51616 2 171196 2 159598 2 136432 2 84454 2 61806 2 136968 2 167442 2 150036 2 23974 2 10064 2 86342 2 146274 2 174318 2 130832 2 118838 2 180...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 99999 0 86548 1 15661 0 30345 1 15659 1 29124 1 23919 1 55755 1 23917 2 68290 1 132201 2 13438 1 132199 3 9859 1 117655 3 13368 1 117653 4 67987 1 162751 4 23781 1 162749 5 24499 1 183011 5 79051 1 183009 6 5988 1 75555 6 12841 1 75553 7 68430 1 29741 7 ...
result:
ok
Test #10:
score: 5
Accepted
time: 6ms
memory: 5972kb
input:
ba73dbf9c7d5e5202834d6a500541c 10000 2 3124 2 3126 2 3128 2 3130 2 3132 2 3134 2 3136 2 3138 2 3140 2 3142 2 3144 2 3146 2 3148 2 3150 2 3152 2 3154 2 3156 2 3158 2 3160 2 3162 2 3164 2 3166 2 3168 2 3170 2 3172 2 3174 2 3176 2 3178 2 3180 2 3182 2 3184 2 3186 2 3188 2 3190 2 3192 2 3194 2 3196 2 31...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 9999 0 1 1 3125 1 2 1 3127 2 3 1 3129 3 4 1 3131 4 5 1 3133 5 6 1 3135 6 7 1 3137 7 8 1 3139 8 9 1 3141 9 10 1 3143 10 11 1 3145 11 12 1 3147 12 13 1 3149 13 14 1 3151 14 15 1 3153 15 16 1 3155 16 17 1 3157 17 18 1 3159 18 19 1 3161 19 20 1 3163 20 21 1 ...
result:
ok
Test #11:
score: 5
Accepted
time: 65ms
memory: 15868kb
input:
ba73dbf9c7d5e5202834d6a500541c 53891 2 3566 2 3568 2 3570 2 3572 2 3574 2 3576 2 3578 2 3580 2 3582 2 3584 2 3586 2 3588 2 3590 2 3592 2 3594 2 3596 2 3598 2 3600 2 3602 2 3604 2 3606 2 3608 2 3610 2 3612 2 3614 2 3616 2 3618 2 3620 2 3622 2 3624 2 3626 2 3628 2 3630 2 3632 2 3634 2 3636 2 3638 2 36...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 53890 0 1 1 3567 1 2 1 3569 2 3 1 3571 3 4 1 3573 4 5 1 3575 5 6 1 3577 6 7 1 3579 7 8 1 3581 8 9 1 3583 9 10 1 3585 10 11 1 3587 11 12 1 3589 12 13 1 3591 13 14 1 3593 14 15 1 3595 15 16 1 3597 16 17 1 3599 17 18 1 3601 18 19 1 3603 19 20 1 3605 20 21 1...
result:
ok
Test #12:
score: 5
Accepted
time: 4ms
memory: 7208kb
input:
ba73dbf9c7d5e5202834d6a500541c 14979 2 4954 2 4956 2 4958 2 4960 2 4962 2 4964 2 4966 2 4968 2 4970 2 4972 2 4974 2 4976 2 4978 2 4980 2 4982 2 4984 2 4986 2 4988 2 4990 2 4992 2 4994 2 4996 2 4998 2 5000 2 5002 2 5004 2 5006 2 5008 2 5010 2 5012 2 5014 2 5016 2 5018 2 5020 2 5022 2 5024 2 5026 2 50...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 14978 0 1 1 4955 1 2 1 4957 2 3 1 4959 3 4 1 4961 4 5 1 4963 5 6 1 4965 6 7 1 4967 7 8 1 4969 8 9 1 4971 9 10 1 4973 10 11 1 4975 11 12 1 4977 12 13 1 4979 13 14 1 4981 14 15 1 4983 15 16 1 4985 16 17 1 4987 17 18 1 4989 18 19 1 4991 19 20 1 4993 20 21 1...
result:
ok
Test #13:
score: 5
Accepted
time: 45ms
memory: 12200kb
input:
ba73dbf9c7d5e5202834d6a500541c 44171 2 36500 2 36502 2 36504 2 36506 2 36508 2 36510 2 36512 2 36514 2 36516 2 36518 2 36520 2 36522 2 36524 2 36526 2 36528 2 36530 2 36532 2 36534 2 36536 2 36538 2 36540 2 36542 2 36544 2 36546 2 36548 2 36550 2 36552 2 36554 2 36556 2 36558 2 36560 2 36562 2 36564...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #14:
score: 5
Accepted
time: 0ms
memory: 3984kb
input:
ba73dbf9c7d5e5202834d6a500541c 1000 2 20406 2 20378 2 37840 2 37702 2 20448 2 37688 2 37780 2 20720 2 38256 2 20612 2 38050 2 20152 2 37880 2 20116 2 20030 2 20526 2 38324 2 20956 2 20852 2 20356 2 37668 2 20292 2 37648 2 20320 2 20078 2 38060 2 38014 2 37738 2 37878 2 20336 2 20472 2 20214 2 38340 ...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #15:
score: 5
Accepted
time: 2ms
memory: 4264kb
input:
ba73dbf9c7d5e5202834d6a500541c 2000 2 19578 2 1754 2 1760 2 130946 2 164378 2 1038 2 20302 2 131788 2 131632 2 164392 2 19868 2 164924 2 131380 2 130972 2 131348 2 1070 2 131568 2 19492 2 19876 2 131606 2 1142 2 1588 2 1424 2 1726 2 131416 2 946 2 20158 2 19574 2 20106 2 1736 2 1186 2 19476 2 164256...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #16:
score: 5
Accepted
time: 177ms
memory: 26272kb
input:
ba73dbf9c7d5e5202834d6a500541c 100000 2 103034 2 75068 2 69976 2 84860 2 113488 2 156808 2 109250 2 119184 2 169250 2 182382 2 161594 2 169232 2 41046 2 87158 2 10192 2 32612 2 84228 2 49708 2 157912 2 160028 2 160234 2 167142 2 22010 2 37360 2 64100 2 113388 2 81460 2 52862 2 77902 2 155958 2 13330...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 99999 0 21451 1 103035 0 22204 1 103033 1 23594 1 75069 1 41977 1 75067 2 35896 1 69977 2 89253 1 69975 3 19303 1 84861 3 83859 1 84859 4 98266 1 113489 4 99175 1 113487 5 4928 1 156809 5 98562 1 156807 6 66778 1 109251 6 45395 1 109249 7 94027 1 119185 ...
result:
ok
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #17:
score: 10
Accepted
time: 0ms
memory: 3808kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 4 4 2 4 4 2 2 2
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 3 0 2 5 3 1 3 1 3 2 3 3 3
result:
ok
Test #18:
score: 10
Accepted
time: 0ms
memory: 4068kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 4 4 2 6 2 4 4 6
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 3 0 3 3 5 0 2 3 3 1 2 1 5
result:
ok
Test #19:
score: 10
Accepted
time: 0ms
memory: 4040kb
input:
ba73dbf9c7d5e5202834d6a500541c 6 4 6 2 4 2 2 4 2 4 4 2 6
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 5 0 4 3 5 1 5 1 5 1 2 1 3 2 3 3 3 3 4 5 3
result:
ok
Test #20:
score: 10
Accepted
time: 0ms
memory: 3804kb
input:
ba73dbf9c7d5e5202834d6a500541c 8 4 2 2 6 4 8 2 4 4 6 2 2 4 4 2 8
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 7 0 6 5 3 0 5 3 3 1 7 1 7 1 3 1 5 2 4 5 7 3 5 1 3 4 6 3 5
result:
ok
Test #21:
score: 10
Accepted
time: 0ms
memory: 3804kb
input:
ba73dbf9c7d5e5202834d6a500541c 8 2 10 2 4 4 4 4 8 2 2 2 8 4 10 4 2
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #22:
score: 10
Accepted
time: 0ms
memory: 3812kb
input:
ba73dbf9c7d5e5202834d6a500541c 4 2 200000 4 199998 2 199998 4 200000
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 3 0 2 1 199999 1 3 5 199999 1 2 3 199999
result:
ok
Test #23:
score: 10
Accepted
time: 470ms
memory: 49472kb
input:
ba73dbf9c7d5e5202834d6a500541c 200000 4 177614 4 159166 2 99950 4 127824 2 158654 4 82678 2 76278 2 198694 4 142000 4 8782 2 49352 2 71260 2 194790 2 87904 2 70702 2 20966 4 161326 2 52586 2 18108 2 36098 2 160702 2 102232 2 67042 2 16712 2 141944 4 27120 4 43282 4 139388 2 144766 4 75542 4 5228 2 1...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 199999 0 59080 5 177615 0 76079 3 177613 1 116266 5 159167 1 113598 3 159165 2 187777 1 99951 2 171355 1 99949 3 83598 3 127825 3 70972 5 127823 4 185799 1 158655 4 18005 1 158653 5 109284 5 82679 5 78787 3 82677 6 41108 1 76279 6 192055 1 76277 7 9969 1...
result:
ok
Test #24:
score: 10
Accepted
time: 0ms
memory: 3808kb
input:
ba73dbf9c7d5e5202834d6a500541c 8 2 183570 4 183570 4 183572 2 183572 2 183578 4 183574 2 183576 4 183576
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 7 0 1 3 183571 0 3 1 183571 1 2 5 183571 2 5 3 183573 4 6 1 183577 5 7 5 183575 6 7 3 183575
result:
ok
Test #25:
score: 10
Accepted
time: 2ms
memory: 4068kb
input:
ba73dbf9c7d5e5202834d6a500541c 1173 2 186526 2 185928 4 185842 4 185780 4 185692 4 186148 4 186016 2 186236 4 185948 4 185626 2 186332 4 186206 2 186480 4 186154 2 186542 2 186504 2 186230 2 186654 2 185902 4 186762 4 186074 2 185804 4 186262 4 185834 2 186224 4 186544 4 185604 2 186300 2 186042 4 1...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 1172 0 585 1 186527 0 43 1 186525 1 798 1 185929 1 234 1 185927 2 902 5 185843 2 517 3 185841 3 563 3 185781 3 480 5 185779 4 474 3 185693 4 936 5 185691 5 670 3 186149 5 341 5 186147 6 176 3 186017 6 689 5 186015 7 844 1 186237 7 489 1 186235 8 201 3 18...
result:
ok
Test #26:
score: 10
Accepted
time: 4ms
memory: 4688kb
input:
ba73dbf9c7d5e5202834d6a500541c 3000 2 109002 2 197108 4 198220 4 197488 4 108286 2 109006 2 197954 2 108586 4 197416 4 197132 4 197374 4 197448 4 197898 2 108330 2 197992 4 109556 2 197598 4 108114 4 109046 2 197128 2 108454 2 108892 2 108110 4 108622 4 197756 2 197924 2 109102 2 198050 2 108460 2 1...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #27:
score: 10
Accepted
time: 5ms
memory: 4580kb
input:
ba73dbf9c7d5e5202834d6a500541c 4000 2 140462 2 140478 2 140596 2 4466 2 172072 2 140272 4 64560 2 64340 4 172244 4 64230 2 57126 4 158866 2 140482 2 64878 4 159028 4 140276 2 56814 2 4364 2 64356 4 64834 4 57096 2 3922 2 172124 4 64542 2 159218 4 140762 2 172112 4 140320 4 56964 4 158988 4 140398 2 ...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
ok
Test #28:
score: 10
Accepted
time: 155ms
memory: 21496kb
input:
ba73dbf9c7d5e5202834d6a500541c 80000 2 77930 2 34884 4 40062 2 34158 2 6130 4 32544 2 51290 2 50478 4 70072 4 69616 2 75800 4 5656 2 4510 2 77766 2 68358 2 42792 4 52374 4 48488 2 75616 2 46682 4 45386 4 28842 2 12918 4 8206 2 20568 2 70466 2 5562 4 61202 2 65046 4 71854 4 9510 2 45910 2 14066 4 608...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 79999 0 13711 1 77931 0 23775 1 77929 1 58477 1 34885 1 33326 1 34883 2 56813 5 40063 2 55865 3 40061 3 64583 1 34159 3 52056 1 34157 4 2150 1 6131 4 47236 1 6129 5 8847 3 32545 5 13806 5 32543 6 42841 1 51291 6 46608 1 51289 7 63755 1 50479 7 21396 1 50...
result:
ok
Test #29:
score: 0
Wrong Answer
time: 239ms
memory: 27052kb
input:
ba73dbf9c7d5e5202834d6a500541c 120000 2 107882 4 86012 4 127996 2 176868 2 178032 4 122930 4 178436 4 160026 4 152606 2 160512 2 84884 2 161726 4 190586 2 149048 2 131608 2 80390 2 155598 4 84696 2 182976 4 158014 4 173998 2 159392 4 128890 4 119618 4 196866 2 97962 4 188404 2 133252 4 166790 4 1593...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
wrong answer Solution announced impossible, but it is possible.
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #82:
score: 20
Accepted
time: 0ms
memory: 4072kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 200000 2 200000 4 199998 2
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 1 2 0 1 200001 3 0 2 199999 3
result:
ok
Test #83:
score: 0
Wrong Answer
time: 0ms
memory: 4064kb
input:
ba73dbf9c7d5e5202834d6a500541c 3 200000 200000 200000 199998 199998 200000
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
wrong answer Solution announced impossible, but it is possible.
Subtask #5:
score: 0
Wrong Answer
Test #108:
score: 0
Wrong Answer
time: 445ms
memory: 43056kb
input:
ba73dbf9c7d5e5202834d6a500541c 200000 82422 100002 100002 52498 82816 2 97624 2 100002 58032 20638 100002 100002 7646 80512 2 2 10584 28426 100002 2 83036 2 64556 47872 100002 55196 2 85350 100002 2 95376 2 23942 12488 100002 83178 2 2 9086 85598 2 100002 78820 100002 10868 98810 2 84182 100002 2 71...
output:
3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix OK 0
result:
wrong answer Solution announced impossible, but it is possible.
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%