QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#649767 | #6109. Similarity Graph | Made_in_Code | WA | 0ms | 3748kb | C++14 | 1.6kb | 2024-10-18 10:08:46 | 2024-10-18 10:08:48 |
Judging History
answer
#include <iostream>
using namespace std;
const int kMaxN = 101;
struct V {
int f;
bool o;
} v[kMaxN * kMaxN / 2];
int n, r[kMaxN][kMaxN], p[kMaxN], q[kMaxN];
bool e[kMaxN][kMaxN];
int GetRoot(int x, bool &o) {
if (v[x].f == x) {
return x;
}
o ^= v[x].o, v[x].o ^= o;
v[x].f = GetRoot(v[x].f, o);
v[x].o ^= o;
return v[x].f;
}
void Merge(int x, int y, bool o) {
x = GetRoot(x, o), y = GetRoot(y, o);
if (x != y) {
v[x].f = y, v[x].o = o;
} else if (o) {
cout << "NO\n";
exit(0);
}
}
int main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
static int o = 0;
cin >> e[i][j], r[i][j] = i < j ? ++o : 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = j + 1; k <= n; k++) {
int c = e[i][j] + e[i][k] + e[j][k];
if (c == 1 || c == 2) {
if (e[i][j] == e[i][k]) {
Merge(r[i][j], r[i][k], 0);
} else if (e[i][j] == e[j][k]) {
Merge(r[i][j], r[j][k], 1);
} else {
Merge(r[i][k], r[j][k], 0);
}
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
bool o = 0;
GetRoot(r[i][j], o);
p[o ? i : j]++, q[o ^ e[i][j] ^ 1 ? i : j]++;
}
}
cout << "YES\n";
for (int i = 1; i <= n; i++) {
cout << ++p[i] << " \n"[i == n];
}
for (int i = 1; i <= n; i++) {
cout << ++q[i] << " \n"[i == n];
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
output:
YES 1 2 3 4 2 4 1 3
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3728kb
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: 3608kb
input:
1 0
output:
YES 1 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
2 0 0 0 0
output:
YES 1 2 2 1
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
2 0 1 1 0
output:
YES 1 2 1 2
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 0 0 0 0 0 0 0 0 0
output:
YES 1 2 3 3 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
3 0 0 0 0 0 1 0 1 0
output:
YES 1 2 3 3 1 2
result:
ok ok
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3748kb
input:
3 0 0 1 0 0 0 1 0 0
output:
NO
result:
wrong answer P did not found the answer