73562024-01-08 10:26:00Error42Kontroll (45)cpp17Wrong answer 8/45109ms53120 KiB
#include <algorithm>
#include <cassert>
#include <climits>
#include <deque>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

using bike_graph_t = vector<vector<int>>;

int const INF = INT_MAX / 3;

struct region_edge {
    int to, w;
};

void dfs_biker_tgraph(
    bike_graph_t const& graph,
    bike_graph_t& tgraph,
    vector<bool>& done,
    int const cur
) {
    done[cur] = true;

    for (int const& neigh : graph[cur]) {
        tgraph[neigh].push_back(cur);

        if (!done[neigh])
            dfs_biker_tgraph(graph, tgraph, done, neigh);
    }
}

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

    int n;
    cin >> n;

    // hopefully the 1 <= n limit is a typo
    assert(n >= 3);

    bike_graph_t bike_graph(n);
    for (int i = 0; i < n - 1; i++) {
        int k;
        cin >> k;

        bike_graph[i].resize(k);

        for (int& x : bike_graph[i]) {
            cin >> x;
            x--;
        }
    }

    bike_graph_t bike_tgraph(n);

    {
        vector<bool> done(n, false);
        dfs_biker_tgraph(bike_graph, bike_tgraph, done, 0);
    }

    vector<int> offset(n);
    offset[0] = n;
    for (int i = 1; i < n; i++)
        offset[i] = offset[i - 1] + bike_graph[i - 1].size() + 1;

    auto const child_region_idx = [&](int const v, int const c) {
        return offset[v] + c;
    };

    vector<vector<region_edge>> region_graph(offset.back() + bike_graph.back().size() + 1);

    auto const region_graph_add_edge = [&](int const u, int const v, int const w) {
        region_graph[u].push_back({ v, w });
        region_graph[v].push_back({ u, w });
    };

    for (int cur = 0; cur < n; cur++) {

        // between cur and child-regions
        for (int i = 0; i < bike_graph[cur].size() + 1; i++)
            region_graph_add_edge(cur, child_region_idx(cur, i), 1);

        for (int i = 0; i < bike_graph[cur].size(); i++) {
            int const neigh = bike_graph[cur][i];

            // between children and child-regions
            region_graph_add_edge(neigh, child_region_idx(cur, i    ), 1);
            region_graph_add_edge(neigh, child_region_idx(cur, i + 1), 1);

            // between child-regions and outer-grandchild-regions
            // - left  side
            if (bike_tgraph[neigh][0]     == cur)
                region_graph_add_edge(child_region_idx(cur, i    ), child_region_idx(neigh, 0                       ), 0);
            // - right side
            if (bike_tgraph[neigh].back() == cur)
                region_graph_add_edge(child_region_idx(cur, i + 1), child_region_idx(neigh, bike_graph[neigh].size()), 0);
        }

    }

    vector<int> from(region_graph.size(), -1);
    vector<int> dist(region_graph.size(), INF);
    deque<int> q;

    q.push_back(child_region_idx(0, 0));
    dist[child_region_idx(0, 0)] = 0;

    while (!q.empty()) {
        int const cur = q.front();
        q.pop_front();

        // cannot block
        // start     or end          or go south of the last vertex
        if (cur == 0 || cur == n - 1 || cur >= offset[n - 1])
            continue;

        for (auto const& e : region_graph[cur]) {
            if (dist[e.to] == INF) {
                dist[e.to] = dist[cur] + e.w;
                from[e.to] = cur;

                if (e.w == 0)
                    q.push_front(e.to);
                else
                    q.push_back(e.to);
            }
        }
    }

#ifdef _DEBUG
    {
        auto const region_v_to_string = [&](int const v) {
            if (v < n)
                return to_string(v);

            int const base = upper_bound(offset.begin(), offset.end(), v) - 1 - offset.begin();
            int const region = v - offset[base];

            return "(" + to_string(base) + " " + to_string(region) + ")";
        };

        for (int u = 0; u < region_graph.size(); u++) {
            cout << region_v_to_string(u) << ": d = " << dist[u] << " f = " << region_v_to_string(from[u]) << " v = { ";
            
            for (auto const e : region_graph[u]) {
                cout << region_v_to_string(e.to) << " " << e.w << ", ";
            }
            cout << "}\n";
        }
    }
#endif

    vector<int> control_points;
    int cur = child_region_idx(0, bike_graph[0].size());

    while (from[cur] != -1) {
        cur = from[cur];

        if (cur < n)
            control_points.push_back(cur);
    }

    assert(cur == child_region_idx(0, 0));

    cout << control_points.size() << "\n";
    for (int const& x : control_points)
        cout << x + 1 << " ";
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base8/45
1Accepted0/03ms1832 KiB
2Wrong answer0/086ms53120 KiB
3Wrong answer0/23ms3116 KiB
4Accepted2/23ms3148 KiB
5Wrong answer0/23ms3572 KiB
6Wrong answer0/33ms3668 KiB
7Wrong answer0/23ms3896 KiB
8Wrong answer0/24ms4856 KiB
9Wrong answer0/24ms5244 KiB
10Wrong answer0/26ms6228 KiB
11Wrong answer0/28ms7572 KiB
12Wrong answer0/24ms5196 KiB
13Wrong answer0/224ms17300 KiB
14Wrong answer0/226ms18500 KiB
15Wrong answer0/263ms31424 KiB
16Wrong answer0/263ms32044 KiB
17Wrong answer0/283ms41440 KiB
18Wrong answer0/275ms41932 KiB
19Wrong answer0/3109ms51376 KiB
20Wrong answer0/3103ms52412 KiB
21Accepted3/363ms45996 KiB
22Accepted3/327ms24112 KiB