Submission #1259147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259147		nqknht	Potemkin cycle (CEOI15_indcyc)	C++20	50 / 100	62 ms	72520 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;
                    if (dis[z] > dis[af] + 1)
                    {
                        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";
    }
}

namespace subfull
{
    int gen(int u, int v)
    {
        return (u - 1) * n + v;
    }
    pair<int, int> decode(int x)
    {
        int u = x / n;
        int v = x % n;
        if (v == 0)
            u--, v = n;
        else 
        u ++;
        return make_pair(u, v);
    }
    bool Ed[1009][1009], icycle = false, vis[1000009];
    vector<ll> G[1000009];

    void dfs(int x)
    {
        if (icycle)
            return;
        vis[x] = true;
        for (auto z : adj[x])
        {
            if (vis[z])
            {
                icycle = true;
                auto w = decode(z);
                cout << w.fi << " ";
                return;
            }
            dfs(z);
            if (icycle)
            {
                auto w = decode(z);
                cout << w.fi << " ";
                return;
            }
        }
    }

    void solve()
    {
        for (int i = 1; i <= m; i++)
        {
            Ed[u[i]][v[i]] = Ed[v[i]][u[i]] = true;
            if (u[i] > v[i])
                swap(u[i], v[i]);
        }
        for (int i = 1; i <= m; i++)
        {
            for (auto z : adj[v[i]])
            {
                if (Ed[u[i]][z] == false)
                    G[gen(u[i], v[i])].push_back(gen(v[i], z));
            }
        }
        for (int i = 1; i <= n * n; i++)
        {
            if (vis[i])
                continue;
            dfs(i);
            if (icycle)
            {
                cout << decode(i).fi << " ";
            }
            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();
    else
        subfull::solve();
    return 0;
}

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