QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #709809 | #6109. Similarity Graph | hhoppitree | WA | 0ms | 3964kb | C++17 | 2.0kb | 2024-11-04 16:56:44 | 2024-11-04 16:56:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int fa[N * N], G[N][N], v[N][N], p[N], q[N], rp[N], rq[N];
int find(int x) {
return (fa[x] == x ? x : fa[x] = find(fa[x]));
}
unsigned int hs(int x) {
mt19937 rnd(x);
return rnd();
}
signed main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%d", &G[i][j]);
}
}
iota(fa + 1, fa + (n * n) + 1, 1);
auto tr = [&](int x, int y) {
return (x - 1) * n + y;
};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
if (i != j && j != k && i != k && G[i][j] == G[i][k] && G[i][j] == !G[j][k]) {
fa[find(tr(i, j))] = find(tr(i, k));
fa[find(tr(j, i))] = find(tr(k, i));
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
v[i][j] = (G[i][j] ^ (hs(find(tr(i, j))) < hs(find(tr(j, i)))));
if (find(tr(i, j)) == find(tr(j, i))) {
puts("NO");
return 0;
}
}
}
iota(p + 1, p + n + 1, 1);
sort(p + 1, p + n + 1, [&](int x, int y) {
return v[x][y];
});
for (int i = 1; i <= n; ++i) {
rp[p[i]] = i;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
v[i][j] = (!G[i][j] ^ (rp[i] < rp[j]));
}
}
iota(q + 1, q + n + 1, 1);
sort(q + 1, q + n + 1, [&](int x, int y) {
return v[x][y];
});
for (int i = 1; i <= n; ++i) {
rq[q[i]] = i;
}
puts("YES");
for (int i = 1; i <= n; ++i) {
printf("%d%c", rp[i], " \n"[i == n]);
}
for (int i = 1; i <= n; ++i) {
printf("%d%c", rq[i], " \n"[i == n]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
input:
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
output:
YES 4 3 2 1 3 1 4 2
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
6 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0
output:
NO
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
1 0
output:
YES 1 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
2 0 0 0 0
output:
YES 1 2 2 1
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
2 0 1 1 0
output:
YES 2 1 2 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
3 0 0 0 0 0 0 0 0 0
output:
YES 2 3 1 2 1 3
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
3 0 0 0 0 0 1 0 1 0
output:
YES 3 1 2 1 2 3
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
3 0 0 1 0 0 0 1 0 0
output:
YES 1 3 2 2 1 3
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
3 0 0 1 0 0 1 1 1 0
output:
YES 1 2 3 2 1 3
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 0 1 0 1 0 0 0 0 0
output:
YES 3 2 1 2 1 3
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
3 0 1 0 1 0 1 0 1 0
output:
YES 3 1 2 2 1 3
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
3 0 1 1 1 0 0 1 0 0
output:
YES 1 3 2 1 2 3
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 0 1 1 1 0 1 1 1 0
output:
YES 2 1 3 2 1 3
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
4 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0
output:
YES 3 2 1 4 3 4 2 1
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
4 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0
output:
YES 1 2 3 4 1 4 3 2
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0
output:
YES 2 3 1 4 1 4 3 2
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
4 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0
output:
YES 3 4 2 1 1 2 4 3
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
4 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
output:
YES 4 3 2 1 1 2 4 3
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
5 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0
output:
YES 4 2 1 3 5 2 3 1 5 4
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
5 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0
output:
YES 4 5 3 2 1 4 3 1 5 2
result:
ok ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0
output:
YES 1 5 2 3 4 3 4 1 5 2
result:
ok ok
Test #22:
score: -100
Wrong Answer
time: 0ms
memory: 3836kb
input:
5 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0
output:
YES 5 3 4 2 1 4 3 5 2 1
result:
wrong answer found wrong p and q