| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 598933 |
2022-07-19T08:07:41 Z |
장태환(#8458) |
Potemkin cycle (CEOI15_indcyc) |
C++17 |
|
1000 ms |
4984 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 = 90;
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++)
{
random_shuffle(link[i].begin(), link[i].end());
maxbe[i].clear();
}
vector<int>od;
for (i = 1; i <= N; i++)
{
od.push_back(i);
}
random_shuffle(od.begin(), od.end());
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;
}
int j, k;
for (j = 0; j < ans.size(); j++)
{
for (k = j+1; k < ans.size()+j; k++)
{
if (k == j + 1 || k == ans.size()+j-1)
{
assert(cn[ans[j%ans.size()]][ans[k%ans.size()]]);
}
else
{
assert(!cn[ans[j%ans.size()]][ans[k%ans.size()]]);
}
}
}
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:97: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]
97 | for (i = 0; i < t.size(); i++)
| ~~^~~~~~~~~~
indcyc.cpp:109: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]
109 | if (ne != maxbe[t[i].first].size())
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (j = 0; j < ans.size(); j++)
| ~~^~~~~~~~~~~~
indcyc.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (k = j+1; k < ans.size()+j; k++)
| ~~^~~~~~~~~~~~~~
indcyc.cpp:126:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | if (k == j + 1 || k == ans.size()+j-1)
| ~~^~~~~~~~~~~~~~~~~
indcyc.cpp:136:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
indcyc.cpp:140:8: warning: unused variable 'd' [-Wunused-variable]
140 | int d;
| ^
indcyc.cpp:139:3: warning: label 'T' defined but not used [-Wunused-label]
139 | T:
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 5 |
Correct |
3 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 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
3 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 |
24 ms |
1448 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
1584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 4 |
Correct |
121 ms |
1652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
1492 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
2988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2260 KB |
Output is correct |
| 3 |
Execution timed out |
1088 ms |
3640 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
455 ms |
2284 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
4984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
