oj.uz

Submission #53902

# Submission time Handle Problem Language Result Execution time Memory
53902 2018-07-01T16:49:24 Z paulica Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 78 ms 4076 KB 
#include <bits/stdc++.h>
using namespace std;

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

#define fi first
#define se second
typedef pair<int, int> pii;

const int MaxN = 1010, MaxR = 1e5 + 10;
int n, r;

vector<pii> e[MaxN];
bool con[MaxN][MaxN];

pii edg[MaxR];
bool vis[MaxR], stk[MaxR];

int pre[MaxR];

void dfs(int x, int y, int id) {
    vis[id] = true;
    stk[id] = true;

    for (pii z : e[y]) {
        if (!con[x][z.fi] && z.fi != x) {
            if (!vis[z.se]) {
                pre[z.se] = id;
                dfs(y, z.fi, z.se);
            } else if (stk[z.se]) {
                vector<int> cyc = {x};
                for (int q = pre[id]; q != z.se; q = pre[q])
                    cyc.push_back(edg[q].fi + edg[q].se - cyc.back());
                if (cyc.back() != y) cyc.push_back(y);
                
                int m = cyc.size();
                for (int len = 3; len < m; len++)
                    for (int i = 0; i < m; i++) {
                        if (con[cyc[i]][cyc[(i + len) % m]]) {
                            for (int j = (i + 1) % m; j != i; j = (j + 1) % m)
                                cout << cyc[j] << " ";
                            cout << cyc[i];

                            exit(0);                
                        }
                    }
            }
        }
    }

    stk[id] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> r;
    
    for (int i = 0; i < r; i++) {
        int x, y;
        cin >> x >> y;
        
        e[x].push_back({y, i});
        e[y].push_back({x, i});

        con[x][y] = con[y][x] = true;

        edg[i] = {x, y};
    }

    for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());

    for (int i = 0; i < r; i++) {
        if (!vis[i]) {
            dfs(edg[i].fi, edg[i].se, i);
        }
    }

    cout << "no";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 452 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 3 ms 728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Correct 3 ms 728 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 736 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 736 KB Output is correct
2 Correct 3 ms 736 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 992 KB Output is correct
2 Correct 3 ms 992 KB Output is correct
3 Correct 5 ms 1120 KB Output is correct
4 Correct 5 ms 1120 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1120 KB Output is correct
2 Correct 4 ms 1120 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3304 KB Output is correct
2 Correct 11 ms 3304 KB Output is correct
3 Correct 38 ms 3308 KB Output is correct
4 Correct 14 ms 3308 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3308 KB Output is correct
2 Correct 12 ms 3308 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3820 KB Output is correct
2 Correct 78 ms 3948 KB Output is correct
3 Correct 30 ms 3948 KB Output is correct
4 Correct 38 ms 4076 KB Output is correct