oj.uz

Submission #696430

# Submission time Handle Problem Language Result Execution time Memory
696430 2023-02-06T13:21:25 Z finn__ Senior Postmen (BOI14_postmen) C++17
100 / 100
 486 ms 105044 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

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

    Edge() {}

    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)
{
    if (g[u][0].v == p)
        return 1;
    return 0;
}

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

    while (!g[u].empty())
    {
        visited[u] = 1;

        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 << ' ';
            delete_edge(edges[e.k]);
            if (x == u)
            {
                cout << '\n';
                x = UINT_MAX;
            }
            return x;
        }
    }

    return UINT_MAX;
}

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);
    edges = vector<Edge>(m);

    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[i] = g[u].back();
    }

    for (unsigned u = 0; u < n; u++)
    {
        find_circuit(u);
    }
}

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 1 ms 216 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 31 ms 7572 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 38 ms 8276 KB Output is correct

Subtask #2
17.0 / 17.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 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 5 ms 1832 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 33 ms 7580 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 37 ms 8288 KB Output is correct
13 Correct 64 ms 19816 KB Output is correct
14 Correct 69 ms 9644 KB Output is correct
15 Correct 47 ms 9784 KB Output is correct
16 Correct 67 ms 19780 KB Output is correct
17 Correct 55 ms 9676 KB Output is correct
18 Correct 70 ms 12020 KB Output is correct

Subtask #3
45.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 0 ms 256 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 33 ms 7612 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 37 ms 8328 KB Output is correct
13 Correct 62 ms 19728 KB Output is correct
14 Correct 50 ms 9688 KB Output is correct
15 Correct 51 ms 9756 KB Output is correct
16 Correct 61 ms 19788 KB Output is correct
17 Correct 63 ms 9640 KB Output is correct
18 Correct 62 ms 11980 KB Output is correct
19 Correct 456 ms 104956 KB Output is correct
20 Correct 416 ms 54108 KB Output is correct
21 Correct 398 ms 49560 KB Output is correct
22 Correct 467 ms 105044 KB Output is correct
23 Correct 186 ms 37664 KB Output is correct
24 Correct 486 ms 53836 KB Output is correct
25 Correct 449 ms 65720 KB Output is correct