Submission #1069300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069300		APROHACK	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	87 ms	3676 KiB

indcyc

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
const int N = 1003, R = 100005;
int n, r;
vector<int>adj[N];

vector<int>ans;
vector<int > backedges[N];
bool connected[N][N];
short vis[N];
const int unvisited = -1;
const int visited = 0;
const int past = 1;

void dfs(int u, int parent, int d){
    vis[u] = visited;
    for(auto v : adj[u]){
        if(v == parent)continue;
        if(vis[v] == unvisited){
            dfs(v, u, d + 1);
        }else if(vis[v] == past)continue;
        else{
            backedges[u].pb(v);
        }
    }
    vis[u] = past;
}
bool isOpS[N], banned[N];
int anterior[N];
int correspondingS[N];
int distancia[N];
short visBfs[N];

bool try_solve(int t, int s){
    return true;
}

bool isBackedge[N];
bool try_solve(int t){
    if(backedges[t].empty())return false;
    //cout << "t = " << t << endl;
    priority_queue<pair<int, pair<int, int > > >pq; // dist, nodo anterior
    vector<int>pisados;
    for(auto s : backedges[t]){
        isBackedge[s] = true;
    }
    for(auto start : adj[t]){
        if(isBackedge[start])continue;
        pq.push({1, {start, t}});
        //cout << "starting at " << start << endl;
        pisados.pb(start);
        visBfs[start] = 1;
    }
    for(auto s : backedges[t]){
        isBackedge[s] = false;
    }

    distancia[t] = 0;
    /// Hay que banear a S?

    pisados.pb(t);
    visBfs[t] = 1;
    int found = -1;
    while(!pq.empty()){
        auto nxt = pq.top();
        int d = min(nxt.ff, 3);
        int u = nxt.ss.ff;
        anterior[u] = nxt.ss.ss;
        distancia[u] = d;
        pq.pop();
        for(auto v : adj[u]){
            if(visBfs[v])continue;
            if(min(d + 1, 3) > distancia[v]){
                pq.push({min(d + 1, 3), {v, u}});
                visBfs[v] = 1;
                pisados.pb(v);
            }
        }
    }

    int sFound = -1;
    for(auto s : backedges[t]){
        //cout << "backedge " << s << endl;
        if(distancia[s] >=3 ){
            found = s;
            break;
        }
    }



    if(found != -1){
        //cout << "camino encontrado" << endl;
        //cout << "t: " << t << endl;
        vector<int>camino;
        camino.push_back(found);
        //cout << "agg " << camino.back()<< endl;
        while(camino.back() != t){
            camino.push_back(anterior[camino.back()]);
            //cout << "agg " << camino.back()<< endl;
        }

        for(int i = 0 ; i < camino.size()-1 ; i ++){
            int addin = camino[i];
            for(int j = 0 ; j < ans.size() ; j ++){
                if(connected[addin][ans[j]]){
                    int eliminamos = ans.size() - (j + 1);
                    for(int x = 0 ; x < eliminamos ; x ++)ans.pop_back();
                    break;
                }
            }
            //cout << "cam " << addin << endl;

            ans.pb(addin);
            //for(auto i : ans)cout << i << " " ;
            //cout << endl;
        }
        ans.pb(t);
        return true;
    }
    for(auto i : pisados){
        visBfs[i] = 0;
        distancia[i] = 0;
    }

    return false;

}

bool respond(int u, int parent, int deepest){
    vis[u] = visited;
    if(try_solve(u))return true;
    for(auto v : adj[u]){
        if(parent == v)continue;
        if(vis[v] == unvisited && respond(v, u, deepest))return true;
    }
    vis[u] = past;
    return false;
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(NULL);
    cin >> n >> r;
    memset(connected, false, sizeof connected);
    for(int i = 0 ; i < r ; i ++){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        connected[u][v] = true;
        connected[v][u] = true;
    }
    for(int i = 1 ; i <= n ; i ++)vis[i] = unvisited;

    dfs(1, -1, 0);
    for(int i = 1 ; i <= n ; i ++)vis[i] = unvisited;
    for(int i = 1 ; i <= n ; i ++)visBfs[i] = 0;
    memset(isBackedge, false, sizeof isBackedge);
    if(!respond(1, -1, -10))cout << "no";
    else{
        for(auto i : ans)cout << i << " ";
    }





}

Compilation message (stderr)

indcyc.cpp: In function 'bool try_solve(int)':
indcyc.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int i = 0 ; i < camino.size()-1 ; i ++){
      |                         ~~^~~~~~~~~~~~~~~~~
indcyc.cpp:109:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             for(int j = 0 ; j < ans.size() ; j ++){
      |                             ~~^~~~~~~~~~~~
indcyc.cpp:85:9: warning: unused variable 'sFound' [-Wunused-variable]
   85 |     int sFound = -1;
      |         ^~~~~~

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