oj.uz

Submission #679934

# Submission time Handle Problem Language Result Execution time Memory
679934 2023-01-09T16:20:33 Z bin9638 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 675 ms 1368 KB 
#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>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("omit-frame-pointer")
#pragma GCC optimize("unroll-loops")

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 508 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 24 ms 504 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 21 ms 412 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1128 KB Output is correct
2 Correct 7 ms 836 KB Output is correct
3 Correct 468 ms 1140 KB Output is correct
4 Correct 203 ms 1056 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 776 KB Output is correct
2 Correct 340 ms 872 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1364 KB Output is correct
2 Correct 20 ms 1364 KB Output is correct
3 Correct 25 ms 1368 KB Output is correct
4 Correct 675 ms 1348 KB Output is correct