# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
598936 |
2022-07-19T08:08:40 Z |
장태환(#8458) |
Potemkin cycle (CEOI15_indcyc) |
C++17 |
|
36 ms |
4436 KB |
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
int num[1010];
int depth[1010];
vector<pair<int, int>> maxbe[1010];
int cnt[1010];
int par[1010];
vector<int>link[1010];
bool arr[1010][1010];
vector<pair<int, int>>t;
int c;
bitset<1024>cn[1010];
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].push_back({ depth[link[n][i]],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]].push_back({ d,n });
t.push_back({ link[n][i],n });
}
}
else
{
dfs(link[n][i], n, d + 1);
}
}
}
int main()
{
srand(time(NULL));
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);
cn[a].set(b);
cn[b].set(a);
}
int T = 1;
while (T--)
{
memset(arr, 0, sizeof(arr));
memset(num, 0, sizeof(num));
memset(depth, 0, sizeof(depth));
t.clear();
memset(par, 0, sizeof(par));
c = 0;
for (i = 1; i <= N; i++)
{
maxbe[i].clear();
}
vector<int>od;
for (i = 1; i <= N; i++)
{
od.push_back(i);
}
for (i = 1; i <= N; i++)
{
if (!num[od[i - 1]])
{
dfs(od[i - 1]);
}
}
for (i = 1; i <= N; i++)
{
sort(maxbe[i].begin(), maxbe[i].end());
}
for (i = 0; i < t.size(); i++)
{
vector<int>ans;
int c = -1;
while (depth[t[i].first] > depth[t[i].second])
{
c++;
ans.push_back(t[i].first);
pair<int, int>xe;
xe.first = depth[t[i].second] + (c == 0);
xe.second = 0;
auto ne = lower_bound(maxbe[t[i].first].begin(), maxbe[t[i].first].end(), xe) - maxbe[t[i].first].begin();
if (ne != maxbe[t[i].first].size())
{
t[i].first = maxbe[t[i].first][ne].second;
}
else
t[i].first = par[t[i].first];
}
ans.push_back(t[i].second);
if (ans.size() <= 3)
{
continue;
}
for (i = 0; i < ans.size(); i++)
cout << ans[i] << ' ';
return 0;
T:
int d;
}
}
cout << "no";
}
Compilation message
indcyc.cpp: In function 'void dfs(int, int, int)':
indcyc.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (i = 0; i < link[n].size(); i++)
| ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (i = 0; i < t.size(); i++)
| ~~^~~~~~~~~~
indcyc.cpp:108:12: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if (ne != maxbe[t[i].first].size())
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
indcyc.cpp:124:8: warning: unused variable 'd' [-Wunused-variable]
124 | int d;
| ^
indcyc.cpp:123:3: warning: label 'T' defined but not used [-Wunused-label]
123 | T:
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1364 KB |
Output is correct |
2 |
Correct |
1 ms |
1364 KB |
Output is correct |
3 |
Correct |
1 ms |
1364 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1364 KB |
Expected integer, but "no" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1364 KB |
Expected integer, but "no" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1492 KB |
Output is correct |
2 |
Correct |
2 ms |
1492 KB |
Output is correct |
3 |
Correct |
3 ms |
1620 KB |
Output is correct |
4 |
Correct |
3 ms |
1620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
1556 KB |
Expected integer, but "no" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
3276 KB |
Output is correct |
2 |
Correct |
7 ms |
2388 KB |
Output is correct |
3 |
Correct |
20 ms |
2948 KB |
Output is correct |
4 |
Correct |
7 ms |
2364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
2316 KB |
Expected integer, but "no" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
4436 KB |
Output is correct |
2 |
Correct |
36 ms |
4172 KB |
Output is correct |
3 |
Correct |
22 ms |
3532 KB |
Output is correct |
4 |
Correct |
21 ms |
3516 KB |
Output is correct |