QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345911 | #3205. Balls and Needles | PetroTarnavskyi# | AC ✓ | 159ms | 35264kb | C++20 | 1.8kb | 2024-03-07 17:01:03 | 2024-03-07 17:01:03 |
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 pair<int, int> PII;
typedef double db;
const int N = 100'447;
bool used[2][N];
set<int> g[2][N];
bool dfs(int t, int v, int p)
{
//cerr << t << ' ' << v << ' ' << p << '\n';
bool cycle = false;
used[t][v] = 1;
for (auto to : g[t][v])
{
if (to == p || to == v)
continue;
if (used[t][to])
return true;
cycle |= dfs(t, to, v);
}
return cycle;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
map<tuple<int, int, int>, int> m1;
map<PII, int> m2;
FOR (i, 0, n)
{
int x1, y1, z1, x2, y2, z2;
cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
if (!m1.count({x1, y1, z1}))
m1[{x1, y1, z1}] = SZ(m1);
if (!m1.count({x2, y2, z2}))
m1[{x2, y2, z2}] = SZ(m1);
if (!m2.count({x1, y1}))
m2[{x1, y1}] = SZ(m2);
if (!m2.count({x2, y2}))
m2[{x2, y2}] = SZ(m2);
int v1 = m1[{x1, y1, z1}];
int v2 = m1[{x2, y2, z2}];
g[0][v1].insert(v2);
g[0][v2].insert(v1);
v1 = m2[{x1, y1}];
v2 = m2[{x2, y2}];
g[1][v1].insert(v2);
g[1][v2].insert(v1);
}
bool ans1 = false;
bool ans2 = false;
FOR (i, 0, SZ(m1))
{
if (!used[0][i])
ans1 |= dfs(0, i, -1);
}
FOR (i, 0, SZ(m2))
{
if (!used[1][i])
{
ans2 |= dfs(1, i, -1);
}
}
if (ans1)
cout << "True closed chains\n";
else
cout << "No true closed chains\n";
if (ans2)
cout << "Floor closed chains\n";
else
cout << "No floor closed chains\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13248kb
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: 12972kb
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: 0ms
memory: 12980kb
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: 13192kb
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: 131ms
memory: 28504kb
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: 99ms
memory: 28668kb
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: 89ms
memory: 28724kb
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: 35ms
memory: 20924kb
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: 39ms
memory: 20948kb
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: 33ms
memory: 22108kb
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: 159ms
memory: 35264kb
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: 151ms
memory: 34764kb
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: 138ms
memory: 29144kb
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: 97ms
memory: 24004kb
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: 136ms
memory: 27136kb
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: 35ms
memory: 21000kb
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