Submission #679926

#	Time	Username	Problem	Language	Result	Execution time	Memory
679926		bin9638	Potemkin cycle (CEOI15_indcyc)	C++17	30 / 100	30 ms	1460 KiB

indcyc

#include<bits/stdc++.h>

using namespace std;
#define N  1010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>

int n,m,ktr[N];
vector<int>g[N];
bitset<N>bit[N],edge[N];
ii dp[N];
deque<int>dq;
vector<int>kq;

struct DSU
{
    int lab[N];

    void init()
    {
        memset(lab,-1,sizeof(lab));
    }

    int root(int u)
    {
        if(lab[u]<0)
            return u;
        return(lab[u]=root(lab[u]));
    }

    void update(int u,int v)
    {
        if((u=root(u))==(v=root(v)))
            return;
        if(lab[u]>lab[v])
            swap(u,v);
        lab[u]+=lab[v];
        lab[v]=u;
    }
}T;

bool clique(bitset<N>bit)
{
    while(bit._Find_first()!=N)
    {
        int pos=bit._Find_first();
        bit[pos]=0;
        if((bit|edge[pos])!=bit)
            return 0;
    }
    return 1;
}

void dijkstra(int S,int T,int k)
{
   // cout<<S<<" "<<T<<endl;
    for(int i=1;i<=n;i++)
        dp[i].fs=1e9;
    dp[S]={0,0};
    dq.push_back(S);
    while(!dq.empty())
    {
        int u=dq.front();
        dq.pop_front();
        for(auto v:g[u])
            if(v!=k&&dp[v].fs>dp[u].fs+1)
            {
                dp[v]={dp[u].fs+1,u};
                dq.pb(v);
            }
    }
    int i=T;
    kq.pb(k);
    kq.pb(T);
    while(i!=S)
    {
        i=dp[i].sc;
      //  cout<<i<<" ";
        kq.pb(i);
    }
    if(kq.size()<4)
        abort();
    for(int i=1;i<kq.size();i++)
        if(edge[kq[i]][kq[i-1]]==0)
            abort();
    if(edge[kq[0]][kq.back()]==0)
        abort();
    for(auto u:kq)cout<<u<<" ";
}

void solve(int u)
{
    memset(ktr,0,sizeof(ktr));
    ktr[u]=1;
    for(auto v:g[u])
        ktr[v]=1;
    T.init();
    for(int i=1;i<=n;i++)
        if(ktr[i]==0)
        {
            for(auto v:g[i])
                if(ktr[v]==0)
                    T.update(i,v);
        }
    for(int i=1;i<=n;i++)
        bit[i].reset();
    for(int i=1;i<=n;i++)
        if(ktr[i]==0)
        {
            int r=T.root(i);
            for(auto v:g[i])
                if(ktr[v]==1&&v!=u)
                    bit[r][v]=1;
        }
    for(int i=1;i<=n;i++)
        if(T.root(i)==i&&!clique(bit[i]))
        {
            for(int l=1;l<=n;l++)
                for(int r=l+1;r<=n;r++)
                    if(bit[i][l]==1&&bit[i][r]==1&&edge[l][r]==0)
                    {
                        dijkstra(l,r,u);
                        exit(0);
                    }
        }
}

int main()
{
    //freopen("A.inp","r",stdin);
 ///   freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        edge[u][v]=edge[v][u]=1;
    }
    for(int i=1;i<=n;i++)
        solve(i);
    cout<<"no";
    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'void dijkstra(int, int, int)':
indcyc.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=1;i<kq.size();i++)
      |                 ~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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