Submission #47266

#	Time	Username	Problem	Language	Result	Execution time	Memory
47266		nickyrio	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	45 ms	27644 KiB

indcyc

//https://oj.uz/problem/view/CEOI15_indcyc
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 1001000
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;

vector<int> e[N];
int n, m, num[N], low[N], cnt, IT[N << 2], d[N];

void Up(int k, int l, int r, int u, int val) {
    if (l == r) {
        IT[k] = val;
        return;
    }
    int m = (l + r) >> 1;
    if (u <= m) Up(k << 1, l, m, u, val);
    else Up(k << 1 | 1, m + 1, r, u, val);
    IT[k] = max(IT[k << 1], IT[k << 1 | 1]);
}

int Max(int k, int l, int r, int u, int v) {
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) return IT[k];
    int m = (l + r) >> 1;
    return max(Max(k << 1, l, m, u, v), Max(k << 1 | 1, m + 1, r, u, v));
}

vector<int> st;
bool dfs(int u, int p) {
    num[u] = ++cnt;
    low[u] = 0;
    st.push_back(u);
    int posLow = 0;
    for (int v : e[u]) if (v != p && num[v]) {
        if (low[u] < num[v]) {
            low[u] = num[v];
            posLow = v;
        }
    }
    if (posLow) {
        if (d[u] - d[posLow] > 2 && Max(1, 1, n, num[posLow], num[u]) < num[posLow]) {
            while (true) {
                cout << st.back() << ' ';
                if (st.back() == posLow) return true;
                st.pop_back();
            }
        }
        Up(1, 1, n, num[u], low[u]);
    }
    for (int v : e[u]) if (v != p && !num[v]) {
        d[v] = d[u] + 1;
        if (dfs(v, u)) return true;
    }
    st.pop_back();
    return false;
}
int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    double stime = clock();
    #else 
        //freopen(taskname".inp","r",stdin);
        //freopen(taskname".out","w",stdout);
    #endif //NERO
    IO;
    cin >> n >> m;
    FOR(i, 1, m) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    FOR(root, 1, n) if (num[root] == 0) {
        if (dfs(root, -1)) return 0;
    }
    cout << "no\n";
    #ifdef NERO
    double etime = clock();
    cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

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