QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #376810 | #6109. Similarity Graph | fairyqq28 | WA | 1ms | 3936kb | C++14 | 1.5kb | 2024-04-04 16:53:57 | 2024-04-04 16:53:58 |
Judging History
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: 100
Accepted
time: 1ms
memory: 3936kb
input:
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
output:
YES 4 3 2 1 3 1 4 2
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
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: 3924kb
input:
1 0
output:
YES 1 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
2 0 0 0 0
output:
YES 2 1 1 2
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 0 1 1 0
output:
YES 2 1 2 1
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
3 0 0 0 0 0 0 0 0 0
output:
YES 3 2 1 1 2 3
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
3 0 0 0 0 0 1 0 1 0
output:
YES 3 2 1 1 3 2
result:
ok ok
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3808kb
input:
3 0 0 1 0 0 0 1 0 0
output:
YES 3 2 1 2 3 1
result:
wrong answer found wrong p and q