oj.uz

Submission #679925

# Submission time Handle Problem Language Result Execution time Memory
679925 2023-01-09T16:12:44 Z bin9638 Potemkin cycle (CEOI15_indcyc) C++17
30 / 100
 32 ms 1492 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>

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,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;
    cout<<k<<" "<<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&&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;
        if(u==v)
            abort();
        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 1 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 496 KB Output is correct
2 Incorrect 1 ms 468 KB Wrong adjacency
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1108 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 892 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1492 KB Wrong adjacency
2 Halted 0 ms 0 KB -