Submission #172833

#	Time	Username	Problem	Language	Result	Execution time	Memory
172833		phillip	Potemkin cycle (CEOI15_indcyc)	C++14	40 / 100	4 ms	540 KiB

indcyc

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int vis[109];
int n,m,ed[109][109];
vector<int>v[109],c;
void ot()
{
    for(int i=0;i<c.size();i++)cout<<c[i]+1<<" ";
    exit(0);
}
void dfs(int x,int par)
{
    c.push_back(x);
    //for(int i=0;i<c.size();i++)cout<<c[i]<<" ";cout<<"\n";
    vis[x]=1;
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i];
        if(y==par||vis[y])continue;
        bool o=1;
        for(int j=1;j<c.size()-1;j++)
        {
            if(ed[y][c[j]]){o=0;break;}
        }
        if(o&&c.size()+1>=4&&ed[c[0]][y])
        {
            c.push_back(y);
            ot();
        }
        else if(o&&(ed[c[0]][y]==0||x==c[0]))dfs(y,x);
    }
    c.pop_back();
}
int main()
{
    cin>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y;
        x--;y--;
        ed[x][y]=1;
        ed[y][x]=1;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        dfs(i,i);
    }
    cout<<"no";
}

Compilation message (stderr)

indcyc.cpp: In function 'void ot()':
indcyc.cpp:9:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<c.size();i++)cout<<c[i]+1<<" ";
                 ~^~~~~~~~~
indcyc.cpp: In function 'void dfs(int, int)':
indcyc.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
indcyc.cpp:22:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<c.size()-1;j++)
                     ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10