| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 598857 |
2022-07-19T06:32:55 Z |
장태환(#8458) |
Potemkin cycle (CEOI15_indcyc) |
C++17 |
|
20 ms |
3680 KB |
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
int num[1010];
int depth[1010];
int maxbe[1010];
int par[1010];
vector<int>link[1010];
bool arr[1010][1010];
vector<pair<int, int>>t;
vector<int>ue[1010], de[1010];
int c;
void dfs(int n, int p = 0, int d = 0)
{
depth[n] = d;
num[n] = ++c;
par[n] = p;
int i;
for (i = 0; i < link[n].size(); i++)
{
if (link[n][i] == p)
continue;
if (num[link[n][i]])
{
if (depth[link[n][i]] < d)
{
if (arr[n][link[n][i]])
continue;
arr[n][link[n][i]] = 1;
maxbe[n] = max(maxbe[n], depth[link[n][i]]);
t.push_back({ n,link[n][i] });
}
else
{
if (arr[link[n][i]][n])
continue;
arr[link[n][i]][n] = 1;
maxbe[link[n][i]] = max(maxbe[link[n][i]], d);
t.push_back({ link[n][i],n });
}
}
else
{
dfs(link[n][i], n, d + 1);
}
}
}
int main()
{
memset(maxbe, -10, sizeof(maxbe));
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
int i;
for (i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
link[a].push_back(b);
link[b].push_back(a);
}
for (i = 1; i <= N; i++)
{
if (!num[i])
{
dfs(i);
}
}
for (i = 0; i < t.size(); i++)
{
vector<int>ans;
int c = 0;
ue[t[i].first].push_back(t[i].second);
de[t[i].second].push_back(t[i].first);
while (depth[t[i].first] > depth[t[i].second])
{
if (maxbe[t[i].first] > depth[t[i].second] || (maxbe[t[i].first] == depth[t[i].second] && c))
{
c = -1;
break;
}
ans.push_back(t[i].first);
t[i].first = par[t[i].first];
c++;
}
if (c >= 0)
{
ans.push_back(t[i].second);
if (ans.size() <= 3)
{
continue;
}
for (i = 0; i < ans.size(); i++)
cout << ans[i] << ' ';
return 0;
}
}
for (i = 1; i <=N; i++)
{
int j;
for (j = 0; j < ue[i].size(); j++)
{
int k;
for (k = j+1; k < ue[i].size(); k++)
{
int a = ue[i][j];
int b = ue[i][k];
if (depth[a] < depth[b])
swap(a, b);
vector<int>ans;
while (depth[a] > depth[b])
{
if (maxbe[a] > depth[b] || (maxbe[a] == depth[b] && c))
{
c = -1;
break;
}
ans.push_back(a);
a = par[a];
c++;
}
ans.push_back(b);
ans.push_back(i);
if (ans.size() <= 3)
continue;
for (i = 0; i < ans.size(); i++)
cout << ans[i] << ' ';
return 0;
}
}
for (j = 0; j < de[i].size(); j++)
{
int k;
for (k = j + 1; k < de[i].size(); k++)
{
int a = de[i][j];
int b = de[i][k];
if (depth[a] < depth[b])
swap(a, b);
vector<int>ans;
while (depth[a] > depth[b])
{
if (maxbe[a] > depth[b] || (maxbe[a] == depth[b] && c))
{
c = -1;
break;
}
ans.push_back(a);
a = par[a];
c++;
}
ans.push_back(b);
ans.push_back(i);
if (ans.size() <= 3)
continue;
for (i = 0; i < ans.size(); i++)
cout << ans[i] << ' ';
return 0;
}
}
}
cout << "no";
}
Compilation message
indcyc.cpp: In function 'void dfs(int, int, int)':
indcyc.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (i = 0; i < link[n].size(); i++)
| ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (i = 0; i < t.size(); i++)
| ~~^~~~~~~~~~
indcyc.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
indcyc.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (j = 0; j < ue[i].size(); j++)
| ~~^~~~~~~~~~~~~~
indcyc.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (k = j+1; k < ue[i].size(); k++)
| ~~^~~~~~~~~~~~~~
indcyc.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
indcyc.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (j = 0; j < de[i].size(); j++)
| ~~^~~~~~~~~~~~~~
indcyc.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (k = j + 1; k < de[i].size(); k++)
| ~~^~~~~~~~~~~~~~
indcyc.cpp:157:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for (i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
356 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
852 KB |
Wrong answer on graph without induced cycle |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
2896 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2004 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2980 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
3680 KB |
Wrong answer on graph without induced cycle |
| 3 |
Halted |
0 ms |
0 KB |
- |
