QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#649770 | #6109. Similarity Graph | Made_in_Code | WA | 1ms | 3744kb | C++14 | 1.7kb | 2024-10-18 10:10:51 | 2024-10-18 10:10:51 |
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++) {
v[i].f = i, p[i] = q[i] = 1;
}
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: 1ms
memory: 3696kb
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: 3616kb
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: 3744kb
input:
2 0 0 0 0
output:
YES 1 2 2 1
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
2 0 1 1 0
output:
YES 1 2 1 2
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3720kb
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: 3668kb
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: 0
Accepted
time: 0ms
memory: 3668kb
input:
3 0 0 1 0 0 0 1 0 0
output:
YES 2 1 3 1 3 2
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 0 0 1 0 0 1 1 1 0
output:
YES 1 2 3 2 1 3
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
3 0 1 0 1 0 0 0 0 0
output:
YES 1 2 3 2 3 1
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 0 1 0 1 0 1 0 1 0
output:
YES 2 1 3 3 1 2
result:
ok ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 0 1 1 1 0 0 1 0 0
output:
YES 1 2 3 1 3 2
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
3 0 1 1 1 0 1 1 1 0
output:
YES 1 2 3 1 2 3
result:
ok ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0
output:
YES 1 2 3 4 3 2 4 1
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
4 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0
output:
YES 1 2 3 4 1 4 3 2
result:
ok ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0
output:
YES 2 3 1 4 1 4 3 2
result:
ok ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0
output:
YES 1 2 3 4 3 4 1 2
result:
ok ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
4 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
output:
YES 1 2 3 4 4 3 1 2
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0
output:
YES 4 2 1 3 5 2 3 1 5 4
result:
ok ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0
output:
YES 1 2 3 4 5 3 2 5 1 4
result:
ok ok
Test #21:
score: -100
Wrong Answer
time: 0ms
memory: 3596kb
input:
5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0
output:
NO
result:
wrong answer P did not found the answer