Submission #1258914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258914		nqknht	Potemkin cycle (CEOI15_indcyc)	C++20	30 / 100	8 ms	2116 KiB

indcyc

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define len(s) (ll) s.size()
#define LS(x) (1 << x)

const ll I = 3e5 + 9;
const ll Z = 1e9 + 7;

using namespace std;

int u[I], v[I], n, m;
vector<int> adj[1506];

namespace sub1
{
    int dis[156], trace[145];
    bool markE[141][156], off[156], check[145];
    queue<int> q;
    void solve()
    {
        for (int i = 1; i <= m; i++)
            markE[u[i]][v[i]] = markE[v[i]][u[i]] = true;
        for (int i = 1; i <= m; i++)
        {
            memset(off, false, sizeof off);
            for (int j = 1; j <= n; j++)
                if (markE[j][u[i]] && markE[j][v[i]])
                {
                    off[j] = true;
                    // cout << j << "\n";
                }
            memset(dis, 10, sizeof dis);
            memset(check, false, sizeof check);
            dis[u[i]] = 0;
            q.push(u[i]);
            while (!q.empty())
            {
                int af = q.front();
                q.pop();
                if (check[af])
                    continue;
                // cout << af << " " << dis[af] << "\n";
                check[af] = true;
                for (auto z : adj[af])
                {
                    if (off[z] || check[z] || (z == v[i] && af == u[i]))
                        continue;
                    dis[z] = dis[af] + 1;
                    trace[z] = af;
                    q.push(z);
                }
            }
            if (dis[v[i]] >= 3 && dis[v[i]] < n)
            {
                cout << v[i] << " ";
                int cur = v[i];
                while (cur != u[i])
                {
                    cur = trace[cur];
                    cout << cur << " ";
                }
                return;
            }
        }
        cout << "no";
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i];
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    // if(n <= 100 && m <= 20000)
    sub1::solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10