QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709138#6109. Similarity GraphhhoppitreeWA 0ms3812kbC++171.9kb2024-11-04 12:11:362024-11-04 12:11:37

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 12:11:37]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3812kb
  • [2024-11-04 12:11:36]
  • 提交

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