Submission #1272940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272940		Gabituss	Potemkin cycle (CEOI15_indcyc)	C++20	0 / 100	66 ms	5108 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

//@formatter:off
using ll = long long;
template<typename T> istream &operator>>(istream &is, vector<T> &a);
template<typename T> ostream &operator<<(ostream &os, vector<T> &a);
//@formatter:on

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#endif

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    vector<int> ord(n);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](int i, int j) {
        return g[i].size() > g[j].size();
    });
    for (int v = 0; v < n; ++v) {
        std::sort(g[v].begin(), g[v].end(), [&](int i, int j) {
            return g[i].size() < g[j].size();
        });
        while (!g[v].empty() && g[v].size() < g[g[v].back()].size()) {
            g[v].pop_back();
        }
    }

    vector<int> used(n);
    for (int u = 0; u < n; ++u) {
        int cntl = 0;
        used[u] = true;
        for (auto v: g[u]) {
            cntl++;
            used[v] = true;
        }
        for (auto v: g[u]) {
            int cntr = 0;
            for (auto v2: g[v]){
                if (used[v2]){
                    cntl--;
                } else {
                    cntr++;
                }
            }

            if (cntl && cntr){
                for (auto v2: g[v]){
                    used[v2] ^= 1;
                }
                for (auto v2: g[u]){
                    if (used[v2]){
                        cout << v2 + 1 << " ";
                        break;
                    }
                }
                for (auto v2: g[v]){
                    used[v2] ^= 1;
                }
                cout << u + 1 << " " << v + 1 << " ";
                for (auto v2: g[v]){
                    if (used[v2] == 0){
                        cout << v2 + 1 << "\n";
                        break;
                    }
                }
                return 0;
            }

            for (auto v2: g[v]){
                if (used[v2]){
                    cntl++;
                } else {
                    cntr--;
                }
            }
        }
        used[u] = false;
        for (auto v: g[u]) {
            cntl--;
            used[v] = false;
        }
    }
    cout << "no" << "\n";
}

// region POZOR
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    for (int i = 0; i < a.size(); i++)
        os << a[i] << " \n"[i == a.size() - 1];
    return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i: a)
        is >> i;
    return is;
}
// endregion

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 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