Submission #510051

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
510051	2022-01-14T15:30:05 Z	CraniXort	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	1 ms	460 KB

indcyc

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

#	Verdict	Memory	Grader output
1	Correct	332 KB	Too short sequence
2	Incorrect	332 KB	Unexpected end of file - token expected
3	Halted	0 KB	-

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Too short sequence

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	460 KB	Too short sequence
2	Incorrect	1 ms	332 KB	Unexpected end of file - token expected

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Too short sequence

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Too short sequence
2	Incorrect	0 ms	332 KB	Unexpected end of file - token expected

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	332 KB	Unexpected end of file - token expected
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Too short sequence
2	Incorrect	0 ms	332 KB	Unexpected end of file - token expected

Subtask #8
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	332 KB	Too short sequence
2	Correct	332 KB	Too short sequence
3	Incorrect	332 KB	Unexpected end of file - token expected
4	Halted	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Too short sequence
2	Incorrect	0 ms	332 KB	Unexpected end of file - token expected

Subtask #10
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	332 KB	Too short sequence
2	Incorrect	332 KB	Unexpected end of file - token expected
3	Halted	0 KB	-