Submission #1259583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259583		nqknht	Potemkin cycle (CEOI15_indcyc)	C++20	20 / 100	169 ms	189684 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)
    {
        // if(u > v) swap(u, v);
        // cout << (u - 1) * n + v << "\n";
        return (u - 1) * n + v;
    }
    pair<int, int> decode(int x)
    {
        int u = x / n;
        int v = x % n;
        if (v == 0)
            v = n;
        else
            u++;
        return make_pair(u, v);
    }
    bool Ed[1009][1009], vis[1000009];
    int icycle = 0, vis1[1000009];

    vector<ll> G[1000009];

    void dfs(int x, int code)
    {
        if (icycle != 0)
            return;
        vis[x] = true;
        vis1[decode(x).fi] = code;
        // cout << x << " " << code << " " << decode(x).fi << " " << decode(x).se << "\n";
        for (auto z : G[x])
        {
            if (vis1[decode(z).fi] == code)
            {
                auto w = decode(z);
                icycle = w.fi;
                // cout << z << "\n";

                // cout << w.fi << " " << w.se << " " << z << "\n";
                cout << w.fi << " ";
                return;
            }
            dfs(z, code);
            if (icycle == -1)
                return;
            else if (icycle > 0)
            {
                auto w = decode(z);
                // cout << w.fi << " " << w.se << " " << z << "\n";

                if (icycle == w.fi)
                    icycle = -1;
                else
                    cout << w.fi << " ";
                return;
            }
        }
        vis1[x] = -code;
    }

    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 && u[i] != z)
                {
                    G[gen(u[i], v[i])].push_back(gen(v[i], z));
                    // cout << u[i] << " " << v[i] << " || " << v[i] << " " << z << "\n";
                }
            }
            swap(u[i], v[i]);
            for (auto z : adj[v[i]])
            {
                if (Ed[u[i]][z] == false && u[i] != z)
                {
                    G[gen(u[i], v[i])].push_back(gen(v[i], z));
                    // cout << u[i] << " " << v[i] << " || " << v[i] << " " << z << "\n";
                }
            }
        }
        for (int i = 1; i <= n * n; i++)
        {
            if (vis[i])
                continue;
            dfs(i, i);
            if (icycle != 0)
            {
                // if (icycle != -1)
                //     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: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 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