Submission #753728

#	Time	Username	Problem	Language	Result	Execution time	Memory
753728		Ronin13	Potemkin cycle (CEOI15_indcyc)	C++14	100 / 100	367 ms	10436 KiB

indcyc

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define pii pair<int,int>
using namespace std;
const int nmax = 1001;
vector <vector <int> > g(nmax);
int used[nmax][nmax];
bool edge[nmax][nmax];
int par[nmax][nmax];
void process_cycle(vector <int> vec){

    int l = 0, r = vec.size() - 1;
    for(int i = 0; i < vec.size(); i++){
        for(int j = i + 3; j < vec.size(); j++){
            if(edge[vec[i]][vec[j]]) {
                l = i, r = j;
                break;
            }
        }
    }
    for(int i = l; i <= r; i++)
        cout << vec[i] << ' ';
    exit(0);
}



void dfs(int x, int y, int e){
    used[x][y] = 1;
    par[x][y] = e;
    for(int to : g[y]){
        if(edge[to][x]) continue;
        if(used[y][to] == 1){
          //  cout << y << ' ' << to << "\n";
           vector <int> cyc;cyc.pb(y);
           while(x != to){
                cyc.pb(x);
               int y1 = par[x][y];
               y = x;
               x = y1;
           }
           cyc.pb(to);
           process_cycle(cyc);
        }
        if(!used[y][to])dfs(y, to, x);
    }
    used[x][y] = 2;
}

int main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        edge[u][v] = edge[v][u] = true;

    }
    for(int i = 1; i <= n; i++){
        edge[i][i] = true;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(!used[i][j]) dfs(i, j, 0);
        }
    }
    cout << "no\n";
}

Compilation message (stderr)

indcyc.cpp: In function 'void process_cycle(std::vector<int>)':
indcyc.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
indcyc.cpp:20:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int j = i + 3; j < vec.size(); j++){
      |                            ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10