oj.uz

Submission #444624

# Submission time Handle Problem Language Result Execution time Memory
444624 2021-07-14T12:59:05 Z prvocislo Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 158 ms 5544 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e3 + 5;
vector<int> g[maxn];
int e[maxn][maxn], vis[maxn], p[maxn];
void dfs(int u, int s, vector<int> &st)
{
    vis[u] = true;
    if (e[u][s])
    {
        st.push_back(u);
        return;
    }
    for (int v : g[u]) if (!vis[v]) dfs(v, s, st);
}
void bfs(int s, int u1, int u2)
{
    memset(p, -1, sizeof(p));
    queue<int> q;
    q.push(u1);
    p[s] = p[u1] = s;
    while (!q.empty())
    {
        int v = q.front(); q.pop();
        for (int i : g[v]) if (p[i] == -1 && (i == u2 || !e[i][s]))
        {
            q.push(i);
            p[i] = v;
        }
    }
    int vr = u2;
    while (p[vr] != vr)
    {
        cout << vr + 1 << " ";
        vr = p[vr];
    }
    cout << s + 1 << endl;
    exit(0);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int n, r;
    cin >> n >> r;
    for (int i = 0, a, b; i < r; i++)
    {
        cin >> a >> b;
        g[--a].push_back(--b), g[b].push_back(a);
        e[a][b] = e[b][a] = true;
    }
    for (int i = 0; i < n; i++) e[i][i] = true;
    for (int i = 0; i < n; i++)
    {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j < n; j++) if (!vis[j] && !e[i][j])
        {
            vector<int> v;
            dfs(j, i, v);
            for (int u : v) vis[u] = false;
            for (int u1 : v) for (int u2 : v) if (!e[u1][u2])
                bfs(i, u1, u2);
        }
    }
    cout << "no\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 3 ms 1624 KB Output is correct
4 Correct 7 ms 1612 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1504 KB Output is correct
2 Correct 6 ms 1484 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5196 KB Output is correct
2 Correct 11 ms 4800 KB Output is correct
3 Correct 158 ms 5232 KB Output is correct
4 Correct 86 ms 4684 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4640 KB Output is correct
2 Correct 84 ms 4612 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3680 KB Output is correct
2 Correct 26 ms 3796 KB Output is correct
3 Correct 24 ms 5476 KB Output is correct
4 Correct 149 ms 5544 KB Output is correct