# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95855 | Kastanda | Potemkin cycle (CEOI15_indcyc) | C++11 | 983 ms | 1400 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 1009;
int n, m, qu[N], P[N];
bitset < N > M, S, is[N];
vector < int > Adj[N];
inline void Prnt(int fxd, int v, int u)
{
M = S = 0;
memset(P, 0, sizeof(P));
for (int &w : Adj[fxd])
M[w] = 1;
int l = 0, r = 0;
qu[r ++] = v;
S[v] = 1;
while (r - l)
{
int nw = qu[l ++];
for (int &w : Adj[nw])
if (w != fxd && !S[w] && !(M[nw] && M[w]))
{
S[w] = 1;
P[w] = nw;
if (!M[w])
qu[r ++] = w;
}
}
if (P[u] == 0)
return ;
vector < int > A;
A.push_back(fxd);
for (; u; u = P[u])
A.push_back(u);
for (int i = 0; i < (int)A.size(); i++)
for (int j = i + 2; j < (int)A.size(); j++)
if ((i != 0 || j != (int)A.size() - 1) && is[A[i]][A[j]])
assert(0);
for (int a : A)
printf("%d ", a);
printf("\n");
exit(0);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int v, u;
scanf("%d%d", &v, &u);
Adj[v].push_back(u);
Adj[u].push_back(v);
is[v][u] = is[u][v] = 1;
}
srand(time(0));
for (int i = 1; i <= n; i++)
random_shuffle(Adj[i].begin(), Adj[i].end());
for (int fxd = 1; fxd <= n; fxd ++)
{
if (clock() >= CLOCKS_PER_SEC * 0.89)
return !printf("no\n");
M = S = 0;
for (int &v : Adj[fxd])
M[v] = 1;
for (int &v : Adj[fxd])
{
int l = 0, r = 0;
qu[r ++] = v;
vector < int > A = {v};
S[v] = 1;
while (r - l)
{
int u = qu[l ++];
for (int &w : Adj[u])
if (w != fxd && !S[w] && !(M[u] && M[w]))
{
S[w] = 1;
if (M[w])
A.push_back(w);
else
qu[r ++] = w;
}
}
for (int i = 0; i < (int)A.size(); i++)
for (int j = i + 1; j < (int)A.size(); j++)
if (!is[A[i]][A[j]])
Prnt(fxd, A[i], A[j]);
}
}
return !printf("no\n");
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |