oj.uz

Submission #753728

# Submission time Handle Problem Language Result Execution time Memory
753728 2023-06-05T19:20:23 Z Ronin13 Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 367 ms 10436 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 3 ms 1232 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2976 KB Output is correct
2 Correct 3 ms 1832 KB Output is correct
3 Correct 4 ms 1620 KB Output is correct
4 Correct 17 ms 3100 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1824 KB Output is correct
2 Correct 11 ms 3052 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6688 KB Output is correct
2 Correct 14 ms 7124 KB Output is correct
3 Correct 367 ms 10048 KB Output is correct
4 Correct 155 ms 9584 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5076 KB Output is correct
2 Correct 234 ms 9564 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2896 KB Output is correct
2 Correct 135 ms 5892 KB Output is correct
3 Correct 29 ms 2688 KB Output is correct
4 Correct 335 ms 10436 KB Output is correct