oj.uz

Submission #851954

# Submission time Handle Problem Language Result Execution time Memory
851954 2023-09-21T00:39:39 Z Nhoksocqt1 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 151 ms 10416 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 1003;

vector<int> adj[MAXN];
int used[MAXN][MAXN], tr[MAXN][MAXN];
int numNode, numEdge;
bool adjc[MAXN][MAXN];

void getPath(const vector<int> &nodes) {
    int l(0), r(sz(nodes) - 1);
    for (int i = 0; i < sz(nodes); ++i) {
        for (int j = i + 3; j < sz(nodes); ++j) {
            if(adjc[nodes[i]][nodes[j]]) {
                l = i, r = j;
                break;
            }
        }
    }

    for (int it = l; it <= r; ++it)
        cout << nodes[it] << ' ';

    exit(0);
}

void dfs(int x, int y, int p) {
    used[x][y] = 1;
    tr[x][y] = p;
    for (int it = 0; it < sz(adj[y]); ++it) {
        int c(adj[y][it]);
        if(adjc[c][x])
            continue;

        if(used[y][c] == 1) {
            vector<int> node;
            while(x != c) {
                node.push_back(y);
                int tmp = tr[x][y];
                y = x;
                x = tmp;
            }

            node.push_back(y);
            node.push_back(x);
            getPath(node);
        } else
            if(!used[y][c]) {
                dfs(y, c, x);
            }
    }

    used[x][y] = 2;
}

void process() {
    cin >> numNode >> numEdge;
    for (int i = 0; i < numEdge; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        adjc[u][v] = adjc[v][u] = 1;
    }

    for (int i = 1; i <= numNode; ++i)
        adjc[i][i] = 1;

    for (int x = 1; x <= numNode; ++x) {
        for (int y = 1; y <= numNode; ++y) {
            if(adjc[x][y] && !used[x][y])
                dfs(x, y, -1);
        }
    }

    cout << "no\n";
}

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

    process();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 4 ms 3932 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9820 KB Output is correct
2 Correct 8 ms 9560 KB Output is correct
3 Correct 35 ms 10068 KB Output is correct
4 Correct 12 ms 9564 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8284 KB Output is correct
2 Correct 34 ms 9700 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7508 KB Output is correct
2 Correct 151 ms 8128 KB Output is correct
3 Correct 13 ms 8024 KB Output is correct
4 Correct 89 ms 10416 KB Output is correct