oj.uz

Submission #332396

# Submission time Handle Problem Language Result Execution time Memory
332396 2020-12-02T08:40:10 Z daniel920712 Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 984 ms 2668 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <time.h>
 
using namespace std;
queue <  pair < int , int >  > BFS;
vector < int > Next[1005];
bool vis[1005];
int Father[1005];
bool have[1005][1005];
int main()
{
    double t=clock();
    int N,M,a,b,i,j,k,ok=0;
    scanf("%d %d",&N,&M);
 
    for(i=0;i<M;i++)
    {
        scanf("%d %d",&a,&b);
        Next[a].push_back(b);
        Next[b].push_back(a);
        have[a][b]=1;
        have[b][a]=1;
    }
    for(i=1;i<=N;i++)
    {
        if((clock()-t)/CLOCKS_PER_SEC>=0.98) break;
        for(auto j:Next[i])
        {
            for(k=1;k<=N;k++) vis[k]=0;
            BFS.push(make_pair(j,1));
            vis[j]=1;
            Father[j]=i;
            while(!BFS.empty())
            {
                a=BFS.front().first;
                b=BFS.front().second;
                BFS.pop();
                if(a==i) continue;
                if(have[a][i])
                {
                    if(b>=3)
                    {
                        while(a!=i)
                        {
                            printf("%d ",a);
                            a=Father[a];
                        }
                        printf("%d ",i);
                        return 0;
                    }
                    else if(b!=1) continue;
                }
 
                for(auto k:Next[a])
                {
                    if(!vis[k])
                    {
                        vis[k]=1;
                        Father[k]=a;
                        BFS.push(make_pair(k,b+1));
                    }
                }
 
            }
 
        }
 
    }
    printf("no\n");
 
 
    return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:21:19: warning: unused variable 'j' [-Wunused-variable]
   21 |     int N,M,a,b,i,j,k,ok=0;
      |                   ^
indcyc.cpp:21:23: warning: unused variable 'ok' [-Wunused-variable]
   21 |     int N,M,a,b,i,j,k,ok=0;
      |                       ^~
indcyc.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
indcyc.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 748 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 93 ms 748 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2284 KB Output is correct
2 Correct 20 ms 1904 KB Output is correct
3 Correct 984 ms 2412 KB Output is correct
4 Correct 981 ms 1900 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1772 KB Output is correct
2 Correct 981 ms 1900 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 2540 KB Output is correct
2 Correct 983 ms 2668 KB Output is correct
3 Correct 185 ms 2668 KB Output is correct
4 Correct 982 ms 2668 KB Output is correct