QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709138 | #6109. Similarity Graph | hhoppitree | WA | 0ms | 3812kb | C++17 | 1.9kb | 2024-11-04 12:11:36 | 2024-11-04 12:11:37 |
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]));
}
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) {
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: 0
Wrong Answer
time: 0ms
memory: 3812kb
input:
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
output:
YES 3 1 4 2 1 2 3 4
result:
wrong answer found wrong p and q