oj.uz

Submission #696214

# Submission time Handle Problem Language Result Execution time Memory
696214 2023-02-05T22:17:42 Z finn__ Senior Postmen (BOI14_postmen) C++17
0 / 100
 1 ms 320 KB 
#include <bits/stdc++.h>
using namespace std;

vector<set<unsigned>> g;
vector<bool> visited;

void find_circuit(unsigned u, unsigned start_node)
{
    if (visited[u] && u == start_node)
        return;
    cout << u + 1 << ' ';
    visited[u] = 1;
    for (auto it = g[u].begin(); it != g[u].end(); it++)
    {
        if (!visited[*it] || *it == start_node)
        {
            unsigned v = *it;
            g[v].erase(u);
            g[u].erase(v);
            find_circuit(v, start_node);
            break;
        }
    }

    visited[u] = 0;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m;
    cin >> n >> m;

    g = vector<set<unsigned>>(n);
    visited = vector<bool>(n, 0);

    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].insert(v - 1);
        g[v - 1].insert(u - 1);
    }

    for (unsigned u = 0; u < n; u++)
    {
        while (!g[u].empty())
        {
            find_circuit(u, u);
            cout << '\n';
        }
    }
}

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Edge does not exist or used 3, 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Incorrect 1 ms 212 KB Edge does not exist or used 3, 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Edge does not exist or used 3, 6
3 Halted 0 ms 0 KB -