oj.uz

Submission #1116048

# Submission time Handle Problem Language Result Execution time Memory
1116048 2024-11-21T08:16:47 Z noyancanturk Potemkin cycle (CEOI15_indcyc) C++17
60 / 100
 103 ms 9244 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int parent[1001];
int find(int i){
  if(i==parent[i])return i;
  return parent[i]=find(parent[i]);
}
void unite(int i,int j){
  i=find(i),j=find(j);
  parent[i]=j;
}

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<=n;i++)parent[i]=i;
  vector<int>v[n+100];
  unordered_set<int>u[n+100];
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x);
    u[x].insert(y);
    u[y].insert(x);
    unite(x,y);
  }
  int layer[n+100]{};
  vector<int>par[n+100];
  queue<int>q;
  for(int i=1;i<=n;i++){
    if(find(i)!=find(0)){
      q.push(i);
      layer[i]=1;
      unite(i,0);
    }
  }
  while(q.size()){
    int node=q.front();
    q.pop();
    for(int j:v[node]){
      if(layer[node]<layer[j])par[j].pb(node);
      if(!layer[j]){
        par[j].pb(node);
        layer[j]=layer[node]+1;
        q.push(j);
      }
    }
  }
  int x=0,y=0,z=0;
  for(int i=1;i<=n;i++){
    for(int j:par[i]){
      for(int k:par[i]){
        if(j==k)continue;
        if(!u[j].count(k)){
          x=i,y=j,z=k;
          break;
        }
      }
      if(x)break;
    }
    if(x)break;
  }
  if(x){
    vector<int>chain1,chain2;
    chain1.pb(x);
    chain1.pb(y);
    chain2.pb(z);
    while(!u[chain1.back()].count(chain2.back())){
      assert(layer[chain1.back()]==layer[chain2.back()]);
      int ng1=par[chain1.back()][0];
      int ng2=par[chain2.back()][0];
      if(u[chain1.back()].count(ng2)){
        chain2.pb(ng2);
        break;
      }
      if(u[chain2.back()].count(ng1)){
        chain1.pb(ng1);
        break;
      }
      chain1.pb(ng1);
      chain2.pb(ng2);
    }
    for(int i=0;i<chain1.size();i++){
      cout<<chain1[i]<<' ';
    }
    for(int i=chain2.size()-1;0<=i;i--){
      cout<<chain2[i]<<' ';
    }
    return 0;
  }
  int w=0;
  for(int i=1;i<=n;i++){
    for(int j:v[i]){
      if(layer[i]!=layer[j])continue;
      int g1=0,g2=0;
      for(int k:par[i]){
        if(!u[j].count(k)){
          g1=k;
          break;
        }
      }
      for(int k:par[j]){
        if(!u[i].count(k)){
          g2=k;
          break;
        }
      }
      if(g1&&g2){
        x=i,y=j,w=g1,z=g2;
        break;
      }
    }
    if(x)break;
  }
  if(x){
    vector<int>chain1,chain2;
    chain1.pb(x);
    chain1.pb(w);
    chain2.pb(y);
    chain2.pb(z);
    while(!u[chain1.back()].count(chain2.back())){
      assert(layer[chain1.back()]==layer[chain2.back()]);
      int ng1=par[chain1.back()][0];
      int ng2=par[chain2.back()][0];
      if(u[chain1.back()].count(ng2)){
        chain2.pb(ng2);
        break;
      }
      if(u[chain2.back()].count(ng1)){
        chain1.pb(ng1);
        break;
      }
      chain1.pb(ng1);
      chain2.pb(ng2);
    }
    for(int i=0;i<chain1.size();i++){
      cout<<chain1[i]<<' ';
    }
    for(int i=chain2.size()-1;0<=i;i--){
      cout<<chain2[i]<<' ';
    }
    return 0;
  }
  cout<<"no";
  return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<chain1.size();i++){
      |                 ~^~~~~~~~~~~~~~
indcyc.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i=0;i<chain1.size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4960 KB Output is correct
2 Correct 13 ms 2384 KB Output is correct
3 Correct 52 ms 5188 KB Output is correct
4 Correct 18 ms 2384 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 2384 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 103 ms 9244 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -