Submission #679932

#	Time	Username	Problem	Language	Result	Execution time	Memory
679932		bin9638	Potemkin cycle (CEOI15_indcyc)	C++17	90 / 100	1088 ms	1492 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;

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)
{
   // 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((ktr[v]==0||v==T)&&dp[v].fs>dp[u].fs+1)
            {
                dp[v]={dp[u].fs+1,u};
                dq.pb(v);
            }
    }
    int i=T;
    cout<<T<<" ";
    while(i!=S)
    {
        i=dp[i].sc;
        cout<<i<<" ";
    }
}

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)
                    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)
                    {
                        cout<<u<<" ";
                        dijkstra(l,r);
                        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;
}

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