QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1239#772331#9246. Dominating Pointxwh_MarvelouscaijianhongFailed.2024-11-22 18:50:442024-11-22 18:50:45

详细

Extra Test:

Accepted
time: 41ms
memory: 6736kb

input:

5000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

NOT FOUND

result:

ok OK, Answer correct.

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#772331#9246. Dominating PointcaijianhongAC ✓123ms7012kbC++231.2kb2024-11-22 18:48:282024-11-22 18:48:28

answer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, deg[5010], d2[5010];
bitset<5010> g[5010];
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n;
  for (int i = 1; i <= n; i++) {
    static char buf[5010];
    cin >> buf;
    for (int j = 1; j <= n; j++) if (buf[j - 1] == '1') g[i][j] = true, ++deg[i];
  }
  vector<int> vec, per(n);
  iota(per.begin(), per.end(), 1);
  sort(per.begin(), per.end(), [&](int i, int j) { return deg[i] > deg[j]; });
  memcpy(d2, deg, sizeof d2);
  sort(d2 + 1, d2 + n + 1);
  //for (int i = 1, pre = 0; i < n; i++) if ((pre += d2[i]) == i * (i - 1) / 2) return cout << "NOT FOUND" << endl, debug("i = %d\n", i), 0;
  for (int i = 0; i < n; i++) {
    bool flag = false;
    for (int j = 0; j < i && !flag; j++) if ((g[per[i]] & g[per[j]]) == g[per[i]]) flag = true, debug("i = %d, j = %d\n", per[i], per[j]);
    if (!flag) vec.push_back(per[i]);
    if (vec.size() >= 3) break;
  }
  if (vec.size() < 3) cout << "NOT FOUND" << endl;
  else cout << vec[0] << " " << vec[1] << " " << vec[2] << endl;
  return 0;
}