QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345952 | #3205. Balls and Needles | KhNURE_KIVI# | AC ✓ | 99ms | 11804kb | C++17 | 3.7kb | 2024-03-07 17:46:50 | 2024-03-07 17:46:51 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
mt19937 rng(4242);
const int max_n = 1e5 + 42, inf = 1000111222;
struct dsu {
int p_or_sz[max_n];
void init(int n) {
for (int i = 0; i < n; ++i) {
p_or_sz[i] = -1;
}
}
int find_set(int v) {
if (p_or_sz[v] < 0) {
return v;
}
return p_or_sz[v] = find_set(p_or_sz[v]);
}
bool union_set(int v1, int v2) {
v1 = find_set(v1);
v2 = find_set(v2);
if (v1 == v2) {
return false;
}
if (-p_or_sz[v1] > -p_or_sz[v2]) {
swap(v1, v2);
}
p_or_sz[v2] += p_or_sz[v1];
p_or_sz[v1] = v2;
return true;
}
};
void solve() {
int k;
cin >> k;
vector<array<int, 6> > av(k);
for(int i = 0; i < k; i++) {
for(int j = 0; j < 6; j++) cin >> av[i][j];
}
vector<array<int, 3> > tri;
vector<array<int, 2> > dva;
for(int i = 0; i < k; i++) {
tri.pb({av[i][0], av[i][1], av[i][2]});
tri.pb({av[i][3], av[i][4], av[i][5]});
dva.pb({av[i][0], av[i][1]});
dva.pb({av[i][3], av[i][4]});
}
sort(all(tri));
tri.resize(unique(all(tri)) - tri.begin());
sort(all(dva));
dva.resize(unique(all(dva)) - dva.begin());
dsu DSU_tri, DSU_dva;
int n = max(len(tri), len(dva));
DSU_tri.init(n);
DSU_dva.init(n);
bool tri_cycle = false, dva_cycle = false;
set<pair<int, int> > tri_edges, dva_edges;
for(auto& x : av) {
int a_tri = lower_bound(all(tri), array<int, 3>{x[0], x[1], x[2]}) - tri.begin();
int b_tri = lower_bound(all(tri), array<int, 3>{x[3], x[4], x[5]}) - tri.begin();
int a_dva = lower_bound(all(dva), array<int, 2>{x[0], x[1]}) - dva.begin();
int b_dva = lower_bound(all(dva), array<int, 2>{x[3], x[4]}) - dva.begin();
if(a_tri > b_tri) swap(a_tri, b_tri);
if(a_dva > b_dva) swap(a_dva, b_dva);
if(a_tri != b_tri && !tri_edges.count({a_tri, b_tri})) {
tri_cycle |= !DSU_tri.union_set(a_tri, b_tri);
tri_edges.insert({a_tri, b_tri});
}
if(a_dva != b_dva && !dva_edges.count({a_dva, b_dva})) {
dva_cycle |= !DSU_dva.union_set(a_dva, b_dva);
dva_edges.insert({a_dva, b_dva});
}
}
if(tri_cycle) cout << "True closed chains";
else cout << "No true closed chains";
cout << '\n';
if(dva_cycle) cout << "Floor closed chains";
else cout << "No floor closed chains";
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
}
/*
KIVI
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4408kb
input:
4 12 12 8 10 5 11 12 12 8 4 14 21 12 12 8 12 20 8 4 14 21 10 5 21
output:
No true closed chains Floor closed chains
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 4376kb
input:
4 1 1 1 2 2 2 2 2 2 1 5 5 9 4 4 9 4 2 9 4 4 9 9 4
output:
No true closed chains No floor closed chains
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 4416kb
input:
3 50 50 50 100 100 100 100 100 100 50 50 90 50 50 90 50 50 50
output:
True closed chains No floor closed chains
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 4640kb
input:
3 1 1 5 1 3 7 1 3 7 4 4 5 4 4 5 1 1 5
output:
True closed chains Floor closed chains
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 63ms
memory: 11792kb
input:
50000 1 1 1 863 729 656 1 1 1 691 941 734 1 1 1 152 900 919 1 1 1 104 698 515 1 1 1 944 617 991 1 1 1 655 88 732 1 1 1 56 627 218 1 1 1 278 40 554 1 1 1 567 478 852 1 1 1 859 303 457 1 1 1 934 797 759 1 1 1 433 524 571 1 1 1 540 504 661 1 1 1 758 180 102 1 1 1 506 442 626 1 1 1 959 132 642 1 1 1 558...
output:
No true closed chains No floor closed chains
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 65ms
memory: 11708kb
input:
50000 874 395 850 323 342 447 874 395 850 510 25 548 874 395 850 940 411 903 874 395 850 748 113 18 874 395 850 491 180 989 874 395 850 798 392 480 874 395 850 318 521 396 874 395 850 526 769 229 874 395 850 216 920 645 874 395 850 105 185 22 874 395 850 762 473 825 874 395 850 338 224 420 874 395 8...
output:
No true closed chains Floor closed chains
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 67ms
memory: 11704kb
input:
50000 964 530 136 212 958 992 964 530 136 421 48 54 964 530 136 109 133 858 964 530 136 860 55 922 964 530 136 457 314 553 964 530 136 992 643 766 964 530 136 466 841 852 964 530 136 970 358 183 964 530 136 562 390 92 964 530 136 42 595 385 964 530 136 44 33 958 964 530 136 300 373 783 964 530 136 8...
output:
No true closed chains No floor closed chains
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 29ms
memory: 9344kb
input:
49949 1 1 1 1 1 2 1 1 2 1 1 3 1 1 3 1 1 4 1 1 4 1 1 5 1 1 5 1 1 6 1 1 6 1 1 7 1 1 7 1 1 8 1 1 8 1 1 9 1 1 9 1 1 10 1 1 10 1 1 11 1 1 11 1 1 12 1 1 12 1 1 13 1 1 13 1 1 14 1 1 14 1 1 15 1 1 15 1 1 16 1 1 16 1 1 17 1 1 17 1 1 18 1 1 18 1 1 19 1 1 19 1 1 20 1 1 20 1 1 21 1 1 21 1 1 22 1 1 22 1 1 23 1 1...
output:
No true closed chains No floor closed chains
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 22ms
memory: 9396kb
input:
49950 1 1 1 1 1 2 1 1 2 1 1 3 1 1 3 1 1 4 1 1 4 1 1 5 1 1 5 1 1 6 1 1 6 1 1 7 1 1 7 1 1 8 1 1 8 1 1 9 1 1 9 1 1 10 1 1 10 1 1 11 1 1 11 1 1 12 1 1 12 1 1 13 1 1 13 1 1 14 1 1 14 1 1 15 1 1 15 1 1 16 1 1 16 1 1 17 1 1 17 1 1 18 1 1 18 1 1 19 1 1 19 1 1 20 1 1 20 1 1 21 1 1 21 1 1 22 1 1 22 1 1 23 1 1...
output:
True closed chains No floor closed chains
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 23ms
memory: 9316kb
input:
49950 1 1 1 1 1 2 1 1 2 1 1 3 1 1 3 1 1 4 1 1 4 1 1 5 1 1 5 1 1 6 1 1 6 1 1 7 1 1 7 1 1 8 1 1 8 1 1 9 1 1 9 1 1 10 1 1 10 1 1 11 1 1 11 1 1 12 1 1 12 1 1 13 1 1 13 1 1 14 1 1 14 1 1 15 1 1 15 1 1 16 1 1 16 1 1 17 1 1 17 1 1 18 1 1 18 1 1 19 1 1 19 1 1 20 1 1 20 1 1 21 1 1 21 1 1 22 1 1 22 1 1 23 1 1...
output:
No true closed chains No floor closed chains
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 96ms
memory: 11688kb
input:
50000 605 562 612 352 220 399 422 451 43 967 354 223 375 981 782 259 314 145 704 588 545 342 532 385 625 228 218 168 338 367 682 936 152 754 877 690 338 676 468 24 433 146 787 604 345 304 78 35 632 598 761 96 180 765 269 757 326 652 305 328 149 981 719 525 503 47 982 943 588 36 522 978 863 693 322 7...
output:
No true closed chains No floor closed chains
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 99ms
memory: 11796kb
input:
50000 800 767 349 765 960 537 434 599 354 73 51 181 302 394 558 946 785 586 222 361 909 148 822 269 916 687 446 919 448 144 202 639 130 975 465 401 584 199 408 431 272 620 649 72 423 550 140 819 876 135 820 293 733 947 647 399 484 217 76 89 825 883 766 850 263 791 30 232 664 460 721 731 319 717 883 ...
output:
No true closed chains No floor closed chains
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 90ms
memory: 11796kb
input:
50000 957 950 999 962 911 930 947 901 917 910 902 979 946 905 910 980 922 950 987 913 998 949 951 929 913 984 955 971 930 991 996 915 983 900 916 938 911 974 983 972 987 937 917 974 930 912 986 912 943 987 969 945 917 940 927 993 951 920 984 993 975 975 992 927 948 901 979 992 935 905 920 939 954 97...
output:
No true closed chains Floor closed chains
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 87ms
memory: 11760kb
input:
50000 527 502 520 512 507 524 512 504 518 500 510 526 511 501 525 512 507 511 520 517 517 504 520 503 522 527 525 504 529 506 512 525 519 517 515 510 509 513 503 506 524 522 505 518 517 502 513 522 514 515 525 517 523 505 505 519 511 526 508 518 515 516 510 511 510 516 500 509 525 502 526 529 524 51...
output:
True closed chains Floor closed chains
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 90ms
memory: 11804kb
input:
50000 524 540 521 518 527 548 513 511 519 531 502 509 521 524 520 506 531 540 545 530 517 521 525 543 520 544 531 526 544 544 506 538 511 509 518 532 537 532 529 533 531 545 522 539 521 519 510 543 511 501 521 531 526 526 525 541 501 529 541 547 545 547 509 510 513 525 546 506 521 506 508 545 547 50...
output:
No true closed chains Floor closed chains
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 41ms
memory: 9324kb
input:
49900 999 999 25 998 998 25 998 998 25 997 997 25 997 997 25 996 996 25 996 996 25 995 995 25 995 995 25 994 994 25 994 994 25 993 993 25 993 993 25 992 992 25 992 992 25 991 991 25 991 991 25 990 990 25 990 990 25 989 989 25 989 989 25 988 988 25 988 988 25 987 987 25 987 987 25 986 986 25 986 986 ...
output:
No true closed chains No floor closed chains
result:
ok 2 lines