oj.uz

Submission #25125

# Submission time Handle Problem Language Result Execution time Memory
25125 2017-06-20T07:20:13 Z 시제연(#1054) Potemkin cycle (CEOI15_indcyc) C++
70 / 100
 1000 ms 4312 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> lis[1100];

int n, m;
int par[1100];
bool chk[1100];
bool adj[1100][1100];

int fin(int a) {return par[a] = ((par[a]==a)?a:fin(par[a]));}
void uni(int a, int b) {
    a = fin(a); b = fin(b);
    par[a] = b;
}

bool vis[1100];
int pa[1100];
void print_path(int v, int q, int r) {
    int i;
    queue<int> qu;
    vis[v] = vis[q] = true;
    pa[v] = -1; pa[q] = v;
    qu.push(q);
    while(!qu.empty()) {
        int here = qu.front();
        qu.pop();
        for (i=0;i<lis[here].size();i++) {
            int there = lis[here][i];
            if (vis[there]||(chk[there]&&there!=r)) continue;
            vis[there] = true;
            qu.push(there);
            pa[there] = here;
            if (there==r) {
                int p = there;
                while(~p) {
                    printf("%d ",p+1);
                    p = pa[p];
                }
                printf("\n");
                return;
            }
        }
    }
    //while(true) printf("!");
}

bool dis[1100];
vector<int> vec;
void dfs(int here, int ori) {
    int i;
    dis[here] = true;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (chk[there]) vec.push_back(there);
        if (chk[there]||dis[there]) continue;
        dfs(there,ori);
    }
}

bool good(int v) {
    int i, j;
    for (i=0;i<vec.size();i++) {
        for (j=i+1;j<vec.size();j++) {
            if (vec[i]!=vec[j]&&!adj[vec[i]][vec[j]]) {
                print_path(v,vec[i],vec[j]);
                return true;
            }
        }
    }
    return false;
}

bool check(int v) {
    int i, j;
    chk[v] = true;
    for (i=0;i<n;i++) par[i] = i;
    for (i=0;i<n;i++) dis[i] = false;
    for (i=0;i<lis[v].size();i++) chk[lis[v][i]] = true;
    for (i=0;i<lis[v].size();i++) {
        int q = lis[v][i];
        for (j=0;j<lis[q].size();j++) {
            int r = lis[q][j];
            if (r==v||!chk[r]) continue;
            adj[q][r] = true;
        }
    }
    for (i=0;i<lis[v].size();i++) {
        int q = lis[v][i];
        for (j=0;j<lis[q].size();j++) {
            int r = lis[q][j];
            if (chk[r]||dis[r]) continue;
            vec.clear();
            dfs(r,q);
            if (good(v)) return true;
        }
    }
    for (i=0;i<lis[v].size();i++) {
        int q = lis[v][i];
        for (j=0;j<lis[q].size();j++) {
            int r = lis[q][j];
            if (r==v||!chk[r]) continue;
            adj[q][r] = false;
        }
    }
    chk[v] = false;
    for (i=0;i<lis[v].size();i++) chk[lis[v][i]] = false;
    return false;
}

int main() {
    int i;

    //freopen("input","r",stdin);

    scanf("%d%d",&n,&m);
    for (i=0;i<m;i++) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--;b--;
        lis[a].push_back(b);
        lis[b].push_back(a);
    }
    for (i=0;i<n;i++) {
        if (check(i)) return 0;
    }
    printf("no\n");

    return 0;
}

Compilation message

indcyc.cpp: In function 'void print_path(int, int, int)':
indcyc.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<lis[here].size();i++) {
                   ^
indcyc.cpp: In function 'void dfs(int, int)':
indcyc.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
indcyc.cpp: In function 'bool good(int)':
indcyc.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<vec.size();i++) {
               ^
indcyc.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=i+1;j<vec.size();j++) {
                     ^
indcyc.cpp: In function 'bool check(int)':
indcyc.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[v].size();i++) chk[lis[v][i]] = true;
               ^
indcyc.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[v].size();i++) {
               ^
indcyc.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<lis[q].size();j++) {
                   ^
indcyc.cpp:89:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[v].size();i++) {
               ^
indcyc.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<lis[q].size();j++) {
                   ^
indcyc.cpp:99:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[v].size();i++) {
               ^
indcyc.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<lis[q].size();j++) {
                   ^
indcyc.cpp:108:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[v].size();i++) chk[lis[v][i]] = false;
               ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:117:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
indcyc.cpp:120:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3244 KB Output is correct
2 Correct 23 ms 3244 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3376 KB Output is correct
2 Correct 0 ms 3376 KB Output is correct
3 Correct 6 ms 3376 KB Output is correct
4 Correct 269 ms 3376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3376 KB Output is correct
2 Correct 199 ms 3380 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3772 KB Output is correct
2 Correct 6 ms 3640 KB Output is correct
3 Execution timed out 1000 ms 3772 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 3656 KB Output is correct
2 Execution timed out 1000 ms 3656 KB Execution timed out

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4312 KB Output is correct
2 Correct 353 ms 4168 KB Output is correct
3 Execution timed out 1000 ms 4196 KB Execution timed out
4 Halted 0 ms 0 KB -