Submission #1272937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272937		Gabituss	Potemkin cycle (CEOI15_indcyc)	C++20	0 / 100	66 ms	5124 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

struct Hash {
    int n;
    const int p = 237, mod = 1e9 + 21;
    vector<int> hash, pw;

    int sum(int a, int b) {
        if (a + b >= mod) return a + b - mod;
        else return a + b;
    }

    int sub(int a, int b) {
        if (a - b < 0)
            return a - b + mod;
        else
            return a - b;
    }

    int mul(int a, int b) {
        return 1ll * a * b % mod;
    }

    int get(int l, int r) {
        return sub(hash[r], mul(hash[l], pw[r - l]));
    }

    Hash(string s) {
        n = s.size();
        hash.resize(n + 1);
        pw.resize(n + 1);
        pw[0] = 1;
        for (int i = 0; i < n; ++i) {
            pw[i + 1] = mul(pw[i], p);
        }
        for (int i = 0; i < n; ++i) {
            hash[i + 1] = sum(mul(hash[i], p), s[i] % mod);
        }
    }
};

struct node {
    array<int, 26> nx;
    int suff, prev;
    ll cnt;

    node() {
        nx.fill(-1);
        suff = prev = -1;
        cnt = 0;
    }
};

struct Suff {
    int a = 0;
    vector<ll> cnt;
    vector<int> term;
    vector<node> S;

    Suff() {
        S.emplace_back();
        cnt.emplace_back();
        S[0].cnt = 1;
    }

    void add(int x) {
        int b = S.size();
        S.emplace_back();
        cnt.emplace_back();

        S[b].prev = a;
        S[b].suff = 0;

        for (; a != -1; a = S[a].suff) {
            if (S[a].nx[x] == -1) {
                S[a].nx[x] = b;
                S[b].cnt += S[a].cnt;
                continue;
            }

            int c = S[a].nx[x];
            if (S[c].prev == a) {
                S[b].suff = c;
                break;
            }

            int d = S.size();
            S.emplace_back();
            cnt.emplace_back();

            S[d].suff = S[c].suff;
            S[c].suff = S[b].suff = d;
            S[d].prev = a;

            S[d].nx = S[c].nx;
            for (; a != -1 && S[a].nx[x] == c; a = S[a].suff) {
                S[d].cnt += S[a].cnt;
                S[c].cnt -= S[a].cnt;
                S[a].nx[x] = d;
            }
            break;
        }

        a = b;
    }

    void init() {
        term.resize((int) S.size());
        int v = a;
        while (v != -1) {
            term[v] = true;
            v = S[v].suff;
        }
        dfs(0);
    }

    void dfs(int v) {
        cnt[v] = term[v];
        for (int i = 0; i < 26; i++) {
            if (S[v].nx[i] == -1) continue;
            if (cnt[S[v].nx[i]] == 0) dfs(S[v].nx[i]);

            cnt[v] += cnt[S[v].nx[i]];
        }
    }

    int move(string s) {
        int v = 0;
        for (auto ch: s) {
            if (S[v].nx[ch - 'a'] == -1) return -1;
            v = S[v].nx[ch - 'a'];
        }
        return v;
    }
};

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;
        for (auto v: g[u]) {
            cntl++;
            used[v] = true;
        }
        for (auto v: g[u]) {
            int cntr = 0;
            cntl--;
            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--;
                }
            }
            cntl++;
        }
        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