QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #709135 | #6109. Similarity Graph | hhoppitree | WA | 0ms | 3964kb | C++17 | 1.8kb | 2024-11-04 12:09:18 | 2024-11-04 12:09:19 |
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];
int find(int x) {
return (fa[x] == x ? x : fa[x] = find(fa[x]));
}
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] ^ (find(tr(i, j)) < 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) {
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
v[i][j] = (!G[i][j] ^ (p[i] < p[j]));
}
}
iota(q + 1, q + n + 1, 1);
sort(q + 1, q + n + 1, [&](int x, int y) {
return v[x][y];
});
puts("YES");
for (int i = 1; i <= n; ++i) {
printf("%d%c", p[i], " \n"[i == n]);
}
for (int i = 1; i <= n; ++i) {
printf("%d%c", q[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: 3936kb
input:
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
output:
YES 2 4 1 3 1 2 3 4
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3588kb
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: 3816kb
input:
2 0 0 0 0
output:
YES 1 2 2 1
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
2 0 1 1 0
output:
YES 2 1 2 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
3 0 0 0 0 0 0 0 0 0
output:
YES 1 2 3 3 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
3 0 0 0 0 0 1 0 1 0
output:
YES 1 3 2 3 2 1
result:
ok ok
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3860kb
input:
3 0 0 1 0 0 0 1 0 0
output:
YES 2 3 1 2 3 1
result:
wrong answer found wrong p and q