QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#709137#6109. Similarity GraphhhoppitreeWA 0ms3896kbC++171.9kb2024-11-04 12:11:012024-11-04 12:11:03

Judging History

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

  • [2024-11-04 12:11:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3896kb
  • [2024-11-04 12:11:01]
  • 提交

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) {
        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];
    });
    for (int i = 1; i <= n; ++i) {
        rp[p[i]] = 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;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3888kb

input:

4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0

output:

YES
3 1 4 2
4 3 2 1

result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

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: 3808kb

input:

1
0

output:

YES
1
1

result:

ok ok

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3896kb

input:

2
0 0
0 0

output:

YES
1 2
1 2

result:

wrong answer found wrong p and q