QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376809#6109. Similarity Graphfairyqq28WA 0ms3904kbC++141.5kb2024-04-04 16:53:382024-04-04 16:53:39

Judging History

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

  • [2024-04-04 16:53:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3904kb
  • [2024-04-04 16:53:38]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 110;
int n, f[10010], p[N], q[N], ans1[N], ans2[N];
bool a[N][N], v[N][N];
inline int id(int x, int y) {return (x - 1) * n + y - 1;}
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
inline bool cmp(int x, int y) {return v[x][y];}
inline void merge(int x, int y) {f[find(x)] = find(y);}

int main(){
    scanf("%d", &n);
    rep(i, 1, n) rep(j, 1, n){
        scanf("%d", &a[i][j]);
        f[id(i, j)] = id(i, j);
    }
    rep(i, 1, n) rep(j, 1, n) rep(k, 1, n)
        if(a[i][j] == a[i][k] && a[i][k] == 1-a[j][k])
            merge(id(i, j), id(i, k)), merge(id(j, i), id(k, i));
    rep(i, 1, n) rep(j, i + 1, n){
        if(find(id(i, j)) == find(id(j, i))){
            puts("NO"); return 0;
        }
        v[i][j] = find(id(i, j)) < find(id(i, j));
        v[j][i] = !v[i][j];
    }
    puts("YES");
    rep(i, 1, n) p[i] = i, q[i] = i;
    sort(p + 1, p + n + 1, cmp);
    rep(i, 1, n) rep(j, i + 1, n){
        printf("pre: %d %d %d\n", i, j, v[i][j]);
        v[i][j] ^= a[i][j] ^ 1;
        printf("now: %d %d %d\n", i, j, v[i][j]);
        v[j][i] = !v[i][j];
    }
    sort(q + 1, q + n + 1, cmp);
    rep(i, 1, n) ans1[p[i]] = i, ans2[q[i]] = i;
    rep(i, 1, n) printf("%d ", ans1[i]); puts("");
    rep(i, 1, n) printf("%d ", ans2[i]); puts("");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3904kb

input:

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

output:

YES
pre: 1 2 0
now: 1 2 0
pre: 1 3 0
now: 1 3 1
pre: 1 4 0
now: 1 4 0
pre: 2 3 0
now: 2 3 1
pre: 2 4 0
now: 2 4 1
pre: 3 4 0
now: 3 4 0
4 3 2 1 
3 1 4 2 

result:

wrong output format Expected integer, but "pre:" found