QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649770#6109. Similarity GraphMade_in_CodeWA 1ms3744kbC++141.7kb2024-10-18 10:10:512024-10-18 10:10:51

Judging History

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

  • [2024-10-18 10:10:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3744kb
  • [2024-10-18 10:10:51]
  • 提交

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