oj.uz

답안 #508784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
508784 2022-01-13T18:43:59 Z CraniXort Potemkin cycle (CEOI15_indcyc) C++17
0 / 100
 449 ms 1048580 KB 
#include <bits/stdc++.h>

// #define fin std::cin
// #define fout std::cout

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

class Graph {
    public:

    std::vector <std::vector <int>> edge;
    std::vector <std::vector <bool>> adj;
    int V;
    Graph() {};

    Graph(int size) {
        V = size;
        edge.resize(V + 1);
        adj.resize(V + 1);
        for(int i = 0; i < adj.size(); i ++)
            adj[i].resize(V + 1);
    }

    void clear() {
        edge.clear();
        adj.clear();
        V = 0;
    }

    void addEdge(int src, int dest) {
        edge[src].push_back(dest);
        edge[dest].push_back(src);
        adj[src][dest] = true;
        adj[dest][src] = true;
    }
};

bool foundSol = false;

bool* visited;

std::vector <int> sol;

void bfs(int root, int start, int end, std::unordered_set <int>& nodes, Graph& graph) {
    std::deque <int> dq;
    dq.push_back(start);

    int dist[graph.V + 1] = {};
    dist[start] = 1;

    while(dq.empty() == false) {
        int node = dq.front();
        dq.pop_front();

        for(int next: graph.edge[node]) {
            if(next == root)
                continue;
            if(nodes.find(next) == nodes.end())
                continue;
            if(dist[next] == 0) {
                dist[next] = dist[node] + 1;
                dq.push_back(next);
            }
        }
    }

    while(end != start) {
        fout << end << ' ';
        for(int next: graph.edge[end])
            if(dist[next] == dist[end] - 1) {
                end = next;
                break;
            }
                
    }
    fout << start << ' ' << root << '\n';
}

void dfs(int& node, int& root, std::unordered_set <int>& nodes,  std::unordered_set <int>& g, std::unordered_set <int>& ngh, Graph& graph) {
    visited[node] = true;
    g.insert(node);
    for(int next: graph.edge[node]) {
        if(nodes.find(next) == nodes.end())
            continue;

        if(visited[next] == false) {
            if(graph.adj[root][next] == false) {
                dfs(next, root, nodes, g, ngh, graph);
            }
            else {
                if(ngh.find(next) != ngh.end())
                    continue;
                for(auto i: ngh) {
                    if(graph.adj[i][next] == false) {
                        foundSol = true;
                        bfs(root, i, next, nodes, graph);
                        return;
                    }
                }
                ngh.insert(next);
            }

        }

        if(foundSol == true)
            return;
    }
}

Graph graph;

void solve(std::unordered_set <int>& nodes) {
    int root = *nodes.begin(), V = graph.V;
    
    for(auto node: nodes)
        visited[node] = false;

    int comp = 0;

    std::vector <std::unordered_set <int>> nextNodes;

    for(auto i: nodes) {
        if(visited[i] == false and graph.adj[root][i] == false and i != root) {
            std::unordered_set <int> g, ngh;
            dfs(i, root, nodes, g, ngh, graph);
            if(foundSol == true)
                return;
            nextNodes.push_back({});
            for(auto j: g)
                nextNodes[comp].insert(j);
            for(auto j: ngh)
                nextNodes[comp].insert(j);  
            comp ++;
        }
    }

    nodes.clear();
    for(int i = 0; i < nextNodes.size(); i ++)
        solve(nextNodes[i]);

}

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

    int V, E;
    fin >> V >> E;

    graph = Graph(V);
    visited = new bool[V+1];

    for(int i = 0, src, dest; i < E; i ++) {
        fin >> src >> dest;
        graph.addEdge(src, dest);
    }

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

    solve(nodes);

    if(foundSol == false)
        fout << "no\n";

    return 0;
}

Compilation message

indcyc.cpp: In constructor 'Graph::Graph(int)':
indcyc.cpp:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0; i < adj.size(); i ++)
      |                        ~~^~~~~~~~~~~~
indcyc.cpp: In function 'void solve(std::unordered_set<int>&)':
indcyc.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::unordered_set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i = 0; i < nextNodes.size(); i ++)
      |                    ~~^~~~~~~~~~~~~~~~~~
indcyc.cpp:114:32: warning: unused variable 'V' [-Wunused-variable]
  114 |     int root = *nodes.begin(), V = graph.V;
      |                                ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 449 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 381 ms 1048580 KB Execution killed with signal 9

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 387 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 375 ms 1048580 KB Execution killed with signal 9

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 374 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 385 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 393 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 386 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 389 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 387 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -