QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649767#6109. Similarity GraphMade_in_CodeWA 0ms3748kbC++141.6kb2024-10-18 10:08:462024-10-18 10:08:48

Judging History

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

  • [2024-10-18 10:08:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3748kb
  • [2024-10-18 10:08:46]
  • 提交

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