oj.uz

답안 #110015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110015 2019-05-08T18:16:52 Z someone_aa Potemkin cycle (CEOI15_indcyc) C++17
60 / 100
 512 ms 2680 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] && (!f_edge[i] || i == j)) {
                visited[i] = true;
                parent[i] = curr;
                q.push(i);
            }
        }
    }

    if(!visited[j]) return false;

    int x = j;
    while(parent[x] != 0) {
        cout<<x<<" ";
        x = parent[x];
    } cout<<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=1;root<=n;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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 512 KB Integer 175 violates the range [1, 100]

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 432 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 768 KB Output is correct
2 Incorrect 4 ms 768 KB Integer 2145 violates the range [1, 300]
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 37 ms 768 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 1940 KB Integer 7240 violates the range [1, 1000]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 301 ms 1664 KB Integer 16750 violates the range [1, 1000]
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 1784 KB Output is correct
2 Correct 292 ms 1804 KB Output is correct
3 Correct 66 ms 2168 KB Output is correct
4 Correct 512 ms 2680 KB Output is correct