oj.uz

Submission #696414

# Submission time Handle Problem Language Result Execution time Memory
696414 2023-02-06T12:52:38 Z finn__ Senior Postmen (BOI14_postmen) C++17
38 / 100
 500 ms 16796 KB 
#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    unsigned u, v, i, j, k; // u <-> i, v <-> j;

    Edge(unsigned u_, unsigned v_, unsigned i_, unsigned j_, unsigned k_)
    {
        u = u_, v = v_, i = i_, j = j_, k = k_;
    }
};

vector<vector<Edge>> g;
vector<Edge> edges;
vector<bool> visited;

void delete_edge(Edge e)
{
    swap(g[e.u][e.i], g[e.u].back());
    swap(g[e.v][e.j], g[e.v].back());
    g[e.u].erase(g[e.u].end() - 1);
    g[e.v].erase(g[e.v].end() - 1);

    if (e.i < g[e.u].size())
    {
        g[e.u][e.i].i = e.i;
        edges[g[e.u][e.i].k] = g[e.u][e.i];
        g[g[e.u][e.i].v][g[e.u][e.i].j].j = e.i;
        edges[g[g[e.u][e.i].v][g[e.u][e.i].j].k] = g[g[e.u][e.i].v][g[e.u][e.i].j];
    }
    if (e.j < g[e.v].size())
    {
        g[e.v][e.j].i = e.j;
        edges[g[e.v][e.j].k] = g[e.v][e.j];
        g[g[e.v][e.j].v][g[e.v][e.j].j].j = e.j;
        edges[g[g[e.v][e.j].v][g[e.v][e.j].j].k] = g[g[e.v][e.j].v][g[e.v][e.j].j];
    }
}

unsigned get_next_edge(unsigned u, unsigned p)
{
    for (size_t i = 0; i < g[u].size(); i++)
        if (g[u][i].v != p)
            return i;
}

Edge find_edge(unsigned u, unsigned v)
{
    for (Edge const &e : g[u])
        if (e.v == v)
            return e;
}

unsigned find_circuit(unsigned u, unsigned p = -1)
{
    if (visited[u])
        return u;
    visited[u] = 1;

    assert(!g[u].empty());
    Edge e = g[u][get_next_edge(u, p)];
    unsigned x = find_circuit(e.v, u);

    visited[u] = 0;
    if (x != UINT_MAX)
    {
        cout << u + 1 << ' ' << flush;
        delete_edge(edges[e.k]);
        if (u == x)
            x = UINT_MAX;
    }

    return x;
}

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

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

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

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

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

Compilation message

postmen.cpp: In function 'unsigned int get_next_edge(unsigned int, unsigned int)':
postmen.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^
postmen.cpp: In function 'Edge find_edge(unsigned int, unsigned int)':
postmen.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 820 KB Output is correct
7 Correct 27 ms 1924 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 158 ms 7836 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 9 ms 628 KB Output is correct
12 Correct 163 ms 8324 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 23 ms 1816 KB Output is correct
8 Correct 4 ms 664 KB Output is correct
9 Correct 158 ms 7784 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 172 ms 8280 KB Output is correct
13 Correct 188 ms 16732 KB Output is correct
14 Correct 184 ms 9628 KB Output is correct
15 Correct 166 ms 9848 KB Output is correct
16 Correct 178 ms 16724 KB Output is correct
17 Correct 193 ms 9820 KB Output is correct
18 Execution timed out 1095 ms 9744 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 33 ms 2028 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 147 ms 7808 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 8 ms 596 KB Output is correct
12 Correct 164 ms 8388 KB Output is correct
13 Correct 176 ms 16732 KB Output is correct
14 Correct 172 ms 9640 KB Output is correct
15 Correct 161 ms 9824 KB Output is correct
16 Correct 180 ms 16796 KB Output is correct
17 Correct 200 ms 9676 KB Output is correct
18 Execution timed out 1083 ms 9856 KB Time limit exceeded
19 Halted 0 ms 0 KB -