Submission #332396

#	Time	Username	Problem	Language	Result	Execution time	Memory
332396		daniel920712	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	984 ms	2668 KiB

indcyc

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10