oj.uz

Submission #1116268

# Submission time Handle Problem Language Result Execution time Memory
1116268 2024-11-21T12:01:13 Z vjudge1 Potemkin cycle (CEOI15_indcyc) C++17
50 / 100
 48 ms 9288 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;
}

vector<int>v[1100];
unordered_set<int>u[1100];
int layer[1100]{};
vector<int>par[1100];

bool visy[1100];
deque<int>resy;
int X,Y;
void dfs(int node){
  resy.pb(node);
  if(node==Y)return;
  visy[node]=1;
  for(int j:v[node]){
    if(layer[j]!=layer[node])continue;
    if(!visy[j]){
      dfs(j);
      if(resy.back()==Y){
        break;
      }
    }
  }
  if(resy.back()==node)resy.pop_back();
}

deque<int>findpath(int x,int y){
  X=x;Y=y;
  dfs(x);
  deque<int>ans;
  ans.pb(resy.front());
  for(int i=1;i<resy.size();i++){
    for(int j=0;j<ans.size();j++){
      if(u[ans[j]].count(ans[i])){
        while(j+1<ans.size())ans.pop_back();
      }
    }
    ans.pb(resy[i]);
  }
  return ans;
}

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<=n;i++)parent[i]=i;
  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);
  }
  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())){
      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;
  }
  for(int i=0;i<=n;i++)parent[i]=i;
  for(int i=1;i<=n;i++){
    for(int j:v[i]){
      if(layer[i]==layer[j])unite(i,j);
    }
  }
  int w=0;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(j<i||layer[i]!=layer[j]||find(i)!=find(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){
    deque<int>chain1,chain2,chain3;
    chain3=findpath(y,x);
    chain1.pb(x);
    chain1.pb(w);
    chain2.pb(y);
    chain2.pb(z);
    while(!u[chain1.back()].count(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]<<' ';
    }
    for(int i=1;i+1<chain3.size();i++){
      cout<<chain3[i]<<' ';
    }
    return 0;
  }
  cout<<"no";
  return 0;
}

Compilation message

indcyc.cpp: In function 'std::deque<int> findpath(int, int)':
indcyc.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=1;i<resy.size();i++){
      |               ~^~~~~~~~~~~~
indcyc.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int j=0;j<ans.size();j++){
      |                 ~^~~~~~~~~~~
indcyc.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while(j+1<ans.size())ans.pop_back();
      |               ~~~^~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<chain1.size();i++){
      |                 ~^~~~~~~~~~~~~~
indcyc.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |     for(int i=0;i<chain1.size();i++){
      |                 ~^~~~~~~~~~~~~~
indcyc.cpp:186:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for(int i=1;i+1<chain3.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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 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
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4944 KB Output is correct
2 Correct 11 ms 2384 KB Output is correct
3 Correct 44 ms 4944 KB Output is correct
4 Correct 18 ms 2640 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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