QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #420949 | #4992. Enigmatic Enumeration | Elfwing11 | TL | 0ms | 3636kb | C++14 | 2.3kb | 2024-05-25 06:06:03 | 2024-05-25 06:06:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using int_t = int32_t;
constexpr int_t INF{numeric_limits<int_t>::max()};
int_t shortestCy(vector<vector<int_t>> graph, int_t node, int_t pare, int_t d, vector<int_t> dis)
{
if (dis[node] != -1)
{
return d - dis[node];
}
dis[node] = d;
int_t shortest = INF;
for (auto i : graph[node])
{
if (i != pare)
{
shortest = min(shortest, shortestCy(graph, i, node, d + 1, dis));
}
}
return shortest;
}
int_t countShortestCycles(vector<vector<int_t>> &graph, int_t shortest)
{
int_t count = 0;
int_t n = graph.size();
for (int start = 0; start < n - (shortest - 1); start++)
{
vector<int_t> dis(n, -1);
queue<pair<int_t, int_t>> que;
que.push({start, -1});
dis[start] = 0;
while (!que.empty())
{
auto [node, pare] = que.front();
que.pop();
for (auto i : graph[node])
{
if (dis[i] == -1 && i >= start)
{ // Not visited
dis[i] = dis[node] + 1;
que.push({i, node});
}
else if (i != pare && dis[node] + dis[i] + 1 == shortest)
{ // Cycle found
count++;
}
}
}
}
return count / 2; // Each cycle is counted twice
}
int main()
{
int_t n, m, a, b;
cin >> n >> m;
vector<vector<int_t>> graph(n);
vector<int_t> parent(n);
int_t total = 0;
for (int_t i = 0; i < n; i++)
{
parent[i] = i;
}
for (int_t i = 0; i < m; i++)
{
cin >> a >> b;
a--;
b--;
graph[a].push_back(b);
graph[b].push_back(a);
while (parent[a] != a)
{
a = parent[a];
}
parent[b] = a;
}
set<int> starts(parent.begin(), parent.end());
int_t shortest = INF;
for (auto i : starts)
{
vector<int_t> dis(n, -1);
shortest = min(shortest, shortestCy(graph, i, i, 0, dis));
}
vector<int_t> dis(n, -1);
total = countShortestCycles(graph, shortest);
cout << total;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
4 4 1 2 2 3 3 4 4 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
output:
10
result:
ok single line: '10'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
6 6 1 2 2 3 3 1 4 5 5 6 6 4
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Time Limit Exceeded
input:
110 5995 109 20 100 23 99 65 106 40 105 62 89 67 57 9 83 38 38 20 28 11 39 28 32 20 108 90 96 50 97 51 80 40 64 48 101 27 84 27 43 35 103 79 70 32 29 28 109 2 43 16 110 94 101 71 84 67 23 19 33 17 107 79 90 33 83 64 57 39 105 46 47 1 80 79 93 67 78 53 34 20 105 15 77 66 65 63 102 57 76 59 47 40 95 4...