oj.uz

Submission #510052

# Submission time Handle Problem Language Result Execution time Memory
510052 2022-01-14T15:30:57 Z CraniXort Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 34 ms 3428 KB 
#include <bits/stdc++.h>

#define maxn 1005
#define inf 10000009
#define fin std::cin
#define fout std::cout

// std::ifstream fin("potemkin.in");
// std::ofstream fout("potemkin.out");

int V, E;

bool adj[maxn][maxn];
bool visited[maxn];
bool ok[maxn];

int dist[maxn], parent[maxn];

std::vector <int> edge[maxn];

void dfs(int node, std::vector <int>& comp) {
    visited[node] = true;
    comp.push_back(node);
    for(auto next: edge[node]) {
        if(visited[next] == true or ok[next] == false)
            continue;
        dfs(next, comp);
    }
}


void solve(std::vector <int> nodes) {
    if(nodes.size() == 0) 
        return;
    int root = nodes[0];

    std::vector <int> neighbours, other;

    for(int i = 1; i < nodes.size(); i ++){
        visited[nodes[i]] = false;
        if(adj[root][nodes[i]] == true)
            neighbours.push_back(nodes[i]);
        else
            other.push_back(nodes[i]);
    }

    for(int i = 1; i <= V; i ++)
        ok[i] = false;
    for(auto i: other)
        ok[i] = true;

    std::vector <std::vector <int>> comps;

    for(auto i: other) {
        if(visited[i] == true)
            continue;
        std::vector <int> aux;
        dfs(i, aux);
        comps.push_back(aux);
    }

    int node1 = -1, node2 = -1;

    for(auto comp: comps) {
        std::vector <int> crtNext;
        for(int next: neighbours) {
            for(int node: comp) {
                if(adj[node][next] == true) {
                    for(int t: crtNext) {
                        if(adj[next][t] == false) {
                            node1 = next;
                            node2 = t;
                            break;
                        }
                    }
                    if(node1 == -1)
                        crtNext.push_back(next);
                    break;
                }
            }
            if(node1 != -1)
                break;
        }

        if(node1 == -1)
            continue;

        for(int i = 1; i <= V; i ++) 
            dist[i] = -1;
        for(int i: comp)
            dist[i] = inf;
        dist[node2] = inf;
        dist[node1] = 1;

        std::queue <int> q;
        q.push(node1);
        while(q.empty() == false) {
            int node = q.front();
            q.pop();

            for(int next: edge[node]) {
                if(dist[next] == inf) {
                    dist[next] = dist[node] + 1;
                    parent[next] = node;
                    q.push(next);
                }
            }
        }

        std::vector <int> sol;
        sol.push_back(node2);
        while(node2 != node1) {
            node2 = parent[node2];
            sol.push_back(node2);
        }

        fout << root << ' ';
        for(auto i: sol)
            fout << i << ' ';
        fout << '\n';
        exit(0);
    }

    solve(neighbours);

    for(auto comp: comps) {
        std::vector <int> aux = comp;
        for(int next: neighbours) {
            for(int node: comp) {
                if(adj[node][next] == true) {
                    aux.push_back(next);
                    break;
                }
            }
        }

        solve(aux);
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    fin >> V >> E;
    for(int i = 0, src, dest; i < E; i ++) {
        fin >> src >> dest;
        adj[src][dest] = adj[dest][src] = true;
        edge[src].push_back(dest);
        edge[dest].push_back(src);
    }

    std::vector <int> nodes;
    for(int i = 1; i <= V; i ++)
        nodes.push_back(i);

    solve(nodes);
    fout << "no\n";

    return 0;
}

Compilation message

indcyc.cpp: In function 'void solve(std::vector<int>)':
indcyc.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 1; i < nodes.size(); i ++){
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 1 ms 616 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 5 ms 844 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1868 KB Output is correct
2 Correct 7 ms 1868 KB Output is correct
3 Correct 20 ms 2036 KB Output is correct
4 Correct 9 ms 1956 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1612 KB Output is correct
2 Correct 12 ms 1720 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1904 KB Output is correct
2 Correct 14 ms 2788 KB Output is correct
3 Correct 20 ms 2944 KB Output is correct
4 Correct 34 ms 3428 KB Output is correct