oj.uz

Submission #47935

# Submission time Handle Problem Language Result Execution time Memory
47935 2018-05-09T08:18:12 Z Extazy Potemkin cycle (CEOI15_indcyc) C++17
40 / 100
 901 ms 2416 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 1007;

int n,m;
vector < int > v[N];
int st[N],pos[N],sz;
bool used[N];
vector < int > ans;
bool have[N][N];
int order[N];

bool cmp_pos(int a, int b) {
  return pos[a]>pos[b];
}

void print() {
  for(int i=0;i<(int)(ans.size());i++) {
    if(i>0) printf(" ");
    printf("%d", ans[i]);
  }
  printf("\n");
}

bool dfs(int node, int from=-1) {
  used[node]=true;
  st[++sz]=node;
  pos[node]=sz;

  int i,len,last=-1;
  vector < int > in;

  for(i=0;i<(int)(v[node].size());i++) if(v[node][i]!=from && pos[v[node][i]]!=-1) {
    in.push_back(v[node][i]);
  }

  sort(in.begin(),in.end(),cmp_pos);

  for(i=0;i<(int)(in.size());i++) {
    if(last==-1) len=pos[node]-pos[in[i]]+1;
    else len=last-pos[in[i]]+2;

    if(len>3) {
      if(last==-1) {
        for(i=pos[in[i]];i<=pos[node];i++) ans.push_back(st[i]);
      }
      else {
        for(i=pos[in[i]];i<=last;i++) ans.push_back(st[i]);
        ans.push_back(node);
      }
      //print();
      return true;
    }
    last=pos[in[i]];
  }

  for(i=0;i<(int)(v[node].size());i++) if(!used[v[node][i]]) if(dfs(v[node][i],node)) {
    return true;
  }

  --sz;
  pos[node]=-1;

  return false;
}

bool check() {
  int i,j;

  for(i=0;i<(int)(ans.size());i++) {
    for(j=i+2;j<(int)(ans.size())-(i==0);j++) {
      if(have[ans[i]][ans[j]]) return false;
    }
  }

  return true;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int it,i,x,y;

  scanf("%d %d", &n, &m);
  for(i=1;i<=m;i++) {
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
    have[x][y]=have[y][x]=true;
  }

  for(i=1;i<=n;i++) {
    order[i]=i;
  }

  while(clock()<=0.90*CLOCKS_PER_SEC) {
    for(i=1;i<=n;i++) {
      random_shuffle(v[i].begin(),v[i].end());
    }
    
    random_shuffle(order+1,order+1+n);

    memset(used,0,sizeof(used));
    memset(pos,-1,sizeof(pos));
    ans.clear();
    sz=0;

    for(i=1;i<=n;i++) if(!used[order[i]]) {
      if(dfs(order[i])) {
        if(check()) {
          print();
          return 0;
        }
        else {
          break;
        }
      }
    }
  }

  printf("no\n");

  return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:85:7: warning: unused variable 'it' [-Wunused-variable]
   int it,i,x,y;
       ^~
indcyc.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 900 ms 852 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 1020 KB Output is correct
2 Correct 620 ms 1040 KB Output is correct
3 Incorrect 900 ms 1100 KB Expected integer, but "no" found
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 900 ms 1100 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 900 ms 2248 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 900 ms 2248 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 901 ms 2416 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -