oj.uz

Submission #47266

# Submission time Handle Problem Language Result Execution time Memory
47266 2018-04-30T04:39:57 Z nickyrio Potemkin cycle (CEOI15_indcyc) C++17
20 / 100
 45 ms 27644 KB 
//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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 21 ms 24048 KB Output is correct
3 Correct 20 ms 24060 KB Output is correct
4 Correct 23 ms 24060 KB Output is correct
5 Correct 24 ms 24060 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24060 KB Expected integer, but "no" found

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24232 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24232 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 24244 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24252 KB Output is correct
2 Incorrect 21 ms 24296 KB Expected integer, but "no" found
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24332 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 25272 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 25272 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 26568 KB Output is correct
2 Correct 45 ms 27420 KB Output is correct
3 Incorrect 37 ms 27644 KB Expected integer, but "no" found
4 Halted 0 ms 0 KB -