oj.uz

Submission #110009

# Submission time Handle Problem Language Result Execution time Memory
110009 2019-05-08T17:56:42 Z someone_aa Potemkin cycle (CEOI15_indcyc) C++17
20 / 100
 53 ms 1884 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 1010;

bool edge[maxn][maxn];
vector<int>g[maxn];
int n, m;

class dsu {
public:
    int n, uparent[maxn], usize[maxn];

    void init(int _n) {
        n = _n;
        for(int i=0;i<=n;i++) {
            usize[i] = 1;
            uparent[i] = i;
        }
    }
    int root(int x) {
        while(x != uparent[x]) {
            x = uparent[x];
        }
        return x;
    }
    bool connected(int u, int v) {
        return root(u) == root(v);
    }
    void unite(int u, int v) {
        u = root(u);
        v = root(v);

        if(u == v) return;
        if(usize[u] > usize[v]) {
            uparent[v] = u;
            usize[u] += usize[v];
        }
        else {
            uparent[u] = v;
            usize[v] += usize[u];
        }
    }
};

dsu x;
bool visited[maxn];
int root;

bool f_edge[maxn];
int parent[maxn];

bool find_path(int root, int i, int j) {
    memset(visited,false,sizeof(visited));
    memset(parent,-1,sizeof(parent));

    parent[i] = root;
    parent[root] = 0;

    visited[root] = true;
    visited[i] = true;
    queue<int>q;
    q.push(i);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();

        for(int i:g[curr]) {
            if(!visited[i]) {
                visited[i] = true;
                parent[i] = curr;
                q.push(i);
            }
        }
    }

    if(!visited[j]) return false;

    int x = j;
    while(x) {
        cout<<x<<" ";
        x = parent[x];
    }
    return true;
}

void dfs(int node) {
    if(visited[node] || f_edge[node]) return;
    visited[node] = true;

    for(int i:g[node]) {
        if(!visited[i]) {
            dfs(i);
            x.unite(i, node);
        }
    }
}

void solve() {
    bool found = false;
    for(root=2;root<=2;root++) {
        memset(f_edge, false,sizeof(f_edge));
        memset(visited,false,sizeof(visited));
        x.init(n);

        visited[root] = true;
        for(int i:g[root]) {
            f_edge[i] = true;
        }

        for(int i=1;i<=n;i++) {
            if(!visited[i]) {
                dfs(i);
            }
        }

        for(int i:g[root]) {
            for(int j:g[root]) {
                if(i < j && !edge[i][j] && x.connected(i, j)) {
                    found = find_path(root, i, j);
                }
            }
            if(found) break;
        }
        if(found) break;
    }
    if(!found) {
        cout<<"no\n";
    }
}

int main() {
    cin>>n>>m;
    int u, v;
    for(int i=0;i<m;i++) {
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        edge[u][v] = edge[v][u] = true;
    }
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Repeated vertex

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Incorrect 4 ms 640 KB Repeated vertex
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 640 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 30 ms 1884 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 16 ms 1664 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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