oj.uz

Submission #1116026

# Submission time Handle Problem Language Result Execution time Memory
1116026 2024-11-21T07:57:36 Z vjudge1 Potemkin cycle (CEOI15_indcyc) C++17
30 / 100
 55 ms 9444 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int lim=1001;

vector<int>v[lim];
unordered_set<int>u[lim];

int main(){
  int n,m;
  cin>>n>>m;
  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);
  }
  int layer[n+1]{};
  vector<int>par[n+1];
  queue<int>q;
  q.push(1);
  layer[1]=1;
  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;
      }
      chain2.pb(ng2);
      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=0;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;
        }
      }
      for(int k:par[j]){
        if(!u[i].count(k)){
          g2=k;
        }
      }
      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())){
      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;
      }
      chain2.pb(ng2);
      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:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<chain1.size();i++){
      |                 ~^~~~~~~~~~~~~~
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++){
      |                 ~^~~~~~~~~~~~~~

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 504 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 508 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 756 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 3 ms 848 KB Output is correct
2 Incorrect 2 ms 840 KB Repeated vertex
3 Halted 0 ms 0 KB -

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 5448 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2640 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 55 ms 9444 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -