Submission #1116048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116048		noyancanturk	Potemkin cycle (CEOI15_indcyc)	C++17	60 / 100	103 ms	9244 KiB

indcyc

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10