QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#669188 | #9246. Dominating Point | mzyx | TL | 0ms | 3560kb | C++20 | 1.5kb | 2024-10-23 17:36:28 | 2024-10-23 17:36:38 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string g[n];
for (int i = 0; i < n; i++) {
cin >> g[i];
}
vector<vector<int>> adj(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '1') {
adj[i].push_back(j);
}
}
}
auto bfs = [&](int u) -> bool {
vector<vector<int>> vis(n, vector<int>(3));
queue<pair<int, int>> q;
q.push({u, 0});
while (!q.empty()) {
auto [x, step] = q.front();
q.pop();
if (vis[x][step]) {
continue;
}
vis[x][step] = 1;
if (step >= 3) {
break;
}
for (auto y : adj[x]) {
if (!vis[y][step + 1]) {
q.push({y, step + 1});
}
}
if (q.size() >= 40*n) {
break;
}
}
// cerr << "f" << "\n";
// cerr << u << "\n";
// for (int i = 0; i < n; i++) {
// cerr << vis[i][0] << " " << vis[i][1] << "\n";
// }
int cnt = 0;
for (int i = 0; i < n; i++) {
if (vis[i][0] || vis[i][1] || vis[i][2]) {
cnt++;
}
}
return cnt >= n;
};
vector<int> ans;
for (int i = 0; i < n; i++) {
if (bfs(i)) {
ans.push_back(i + 1);
}
if (ans.size() >= 3) {
break;
}
}
if (ans.size() >= 3) {
cout << ans[0] << " " << ans[1] << " " << ans[2] << "\n";
} else {
cout << "NOT FOUND" << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
6 011010 000101 010111 100001 010100 100010
output:
1 3 4
result:
ok OK, Answer correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 011 001 000
output:
NOT FOUND
result:
ok OK, Answer correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
3 010 001 100
output:
1 2 3
result:
ok OK, Answer correct.
Test #4:
score: -100
Time Limit Exceeded
input:
4994 0100001010011001010101110010101000111101111100100001110010000111100000000100110100101000001010100000010010010110110110111010010010100110100000110110111001010111010111010111011001000101001000010001010111110000000100001100000111100011001010010111011100111010101110011000010111101011111110001111110...