oj.uz

Submission #70110

# Submission time Handle Problem Language Result Execution time Memory
70110 2018-08-22T11:12:15 Z Bodo171 Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 255 ms 6440 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=1005;
bool ad[nmax][nmax];
vector<int> v[nmax],cyc,l;
int lev[nmax],prec[nmax],viz[nmax],d[nmax],valid[nmax],q[nmax];
int i,n,m,u,p,x,nod,a,b,start;
void construieste(int A,int B)
{
    while(A!=B)
    {
        cyc.push_back(A);
        A=prec[A];
    }
    cyc.push_back(B);
    cyc.push_back(start);
}
void dfs(int x)
{
    viz[x]=1;if(ad[start][x])l.push_back(x);
    if(!ad[start][x])
      for(int i=0;i<v[x].size();i++)
        if(!viz[v[x][i]])
    {
        dfs(v[x][i]);
    }
}
void get_cyc(int A,int B)
{
    for(int i=1;i<=n;i++)
        valid[i]=1;
    valid[start]=0;
    for(int i=0;i<v[start].size();i++)
        valid[v[start][i]]=0;
    valid[A]=valid[B]=1;
    q[u=1]=B;d[B]=1;
    for(p=1;p<=u;p++)
    {
         x=q[p];
         for(int i=0;i<v[x].size();i++)
         {
             nod=v[x][i];
             if((!d[nod])&&valid[nod])
             {
                 d[nod]=d[x]+1;
                 q[++u]=nod;
                 prec[nod]=x;
             }
         }
    }
    construieste(A,B);
}
void solve()
{
    for(i=1;i<=n;i++)
        prec[i]=viz[i]=0;
    u=0;
    for(int i=1;i<=n;i++)
        if((!viz[i])&&(!ad[start][i]))
      {
          l.clear();
          dfs(i);
          for(int j=0;j<l.size();j++)
            for(int k=j+1;k<l.size();k++)
          {
              if(!ad[l[j]][l[k]])
              {
                  get_cyc(l[j],l[k]);
                  return;
              }
          }
      }
}
int main()
{
  //  freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;
        ad[a][b]=ad[b][a]=1;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++)
        ad[i][i]=1;
    for(start=1;start<=n&&cyc.size()==0;start++)
    {
        solve();
    }
    if(!cyc.size())
    {
        cout<<"no";
    }
    else
    {
        for(i=0;i<cyc.size();i++)
            cout<<cyc[i]<<' ';
    }
    return 0;
}

Compilation message

indcyc.cpp: In function 'void dfs(int)':
indcyc.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<v[x].size();i++)
                   ~^~~~~~~~~~~~
indcyc.cpp: In function 'void get_cyc(int, int)':
indcyc.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[start].size();i++)
                 ~^~~~~~~~~~~~~~~~
indcyc.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for(int i=0;i<v[x].size();i++)
                      ~^~~~~~~~~~~~
indcyc.cpp: In function 'void solve()':
indcyc.cpp:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(int j=0;j<l.size();j++)
                       ~^~~~~~~~~
indcyc.cpp:67:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=j+1;k<l.size();k++)
                           ~^~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<cyc.size();i++)
                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 2 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 3 ms 600 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1296 KB Output is correct
2 Correct 3 ms 1296 KB Output is correct
3 Correct 5 ms 1296 KB Output is correct
4 Correct 12 ms 1312 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1320 KB Output is correct
2 Correct 9 ms 1472 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2920 KB Output is correct
2 Correct 22 ms 2920 KB Output is correct
3 Correct 253 ms 3436 KB Output is correct
4 Correct 123 ms 3436 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3572 KB Output is correct
2 Correct 159 ms 3592 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4384 KB Output is correct
2 Correct 38 ms 5220 KB Output is correct
3 Correct 28 ms 5948 KB Output is correct
4 Correct 255 ms 6440 KB Output is correct