#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 = min(30000000/N/N,10000);
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;
}
for (i = 0; i < ans.size(); i++)
cout << ans[i] << ' ';
return 0;
}
}
for (i = 1; i <= N; i++)
{
int j;
for (j = i+1; j <= N; j++)
{
if (cn[i][j])
continue;
vector<int>r;
int k;
for (k = 0; k < link[i].size(); k++)
{
if (cn[j][link[i][k]])
r.push_back(link[i][k]);
}
for (k = 0; k < r.size(); k++)
{
int l;
for (l = k+1; l < r.size(); l++)
{
if (!cn[r[k]][r[l]])
{
cout << i << ' ' << r[k] << ' ' << j << ' ' << r[l];
return 0;
}
}
}
}
}
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:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
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 (k = 0; k < link[i].size(); k++)
| ~~^~~~~~~~~~~~~~~~
indcyc.cpp:141:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (k = 0; k < r.size(); k++)
| ~~^~~~~~~~~~
indcyc.cpp:144:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (l = k+1; l < r.size(); l++)
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
269 ms |
1368 KB |
Output is correct |
| 3 |
Correct |
282 ms |
1376 KB |
Output is correct |
| 4 |
Correct |
256 ms |
1364 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 8 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
283 ms |
1368 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
120 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
599 ms |
1436 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
194 ms |
1592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 4 |
Correct |
418 ms |
1776 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
159 ms |
1616 KB |
Output is correct |
| 2 |
Correct |
200 ms |
1560 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
3024 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2232 KB |
Output is correct |
| 3 |
Correct |
453 ms |
3516 KB |
Output is correct |
| 4 |
Correct |
178 ms |
2560 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
289 ms |
2264 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1043 ms |
5012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
