Submission #1036733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036733		LaviniaTornaghi	Train (APIO24_train)	C++17	10 / 100	497 ms	311364 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

struct Departure { int idx, start, time_start; };
struct Meal { int l, r; };
struct Arrival { int time, idx; };

struct SegTree {
    struct Node {
        long long sum;
        vector<int> *valid;
        unordered_set<int> visited;
        Departure dep;
        int mi_time, ma_time;

        int nb, ne;
        Node *lc, *rc;

        Node(Departure dep, long long sum, int nb, int ne)
            : sum(sum), dep(dep), mi_time(dep.time_start), ma_time(dep.time_start), nb(nb), ne(ne), lc(nullptr), rc(nullptr)
        {
            valid = new vector<int>;
            valid->push_back(dep.start);
        }

        Node(Node *lc, Node *rc)
            : sum(lc->sum + rc->sum), mi_time(lc->mi_time), ma_time(rc->ma_time), ne(rc->ne), lc(lc), rc(rc)
        {
            valid = new vector<int>;
            merge(lc->valid->begin(), lc->valid->end(), rc->valid->begin(), rc->valid->end(), back_inserter(*valid));
        }
    };

    vector<Node*> roots;

    Node* build(const vector<Departure> &dep, int nb, int ne) {
        if (nb + 1 == ne) return new Node(dep[nb], 0, nb, ne);
        Node *lc = build(dep, nb, (nb + ne) / 2);
        Node *rc = build(dep, (nb + ne) / 2, ne);
        return new Node(lc, rc);
    }

    Node* add_meal(int r, Node *node) {
        if (node->ma_time < r) return node;

        Node *new_node = new Node(*node);
        new_node->sum++;
        
        if (new_node->lc) {
            if (node->lc->ma_time >= r) new_node->lc = add_meal(r, node->lc);
            else new_node->rc = add_meal(r, node->rc);
        }

        return new_node;
    }

    vector<pair<Node*, long long>> get_continuation(int r, Node *node, long long acc = 0) {
        if (!node->lc) {
            if (node->ma_time >= r) return {{node, acc}};
            else return {};
        }
        if (node->lc->ma_time >= r) {
            vector<pair<Node*, long long>> c = get_continuation(r, node->lc, acc);
            c.emplace_back(node->rc, acc + node->lc->sum);
            return c;
        } else {
            return get_continuation(r, node->rc, acc + node->lc->sum);
        }
    };

    void debug(Node *node, int d = 0) {
        if (!node) return;

        cerr << string(2 * d, ' ')
             << node << " "
             << node->sum << " ("
             << node->dep.idx << " " << node->dep.start << " " << node->dep.time_start << ") (";
        
        for (auto x: *node->valid)
            cerr << x << " ";
        cerr << ")\n";

        debug(node->lc, d + 1);
        debug(node->rc, d + 1);
    }

    void debug(int root) { debug(roots[root]); }
    int get_curr_root() { return roots.size() - 1; }
    void add_meal(int r) { roots.push_back(add_meal(r, roots.back())); }

    SegTree(const vector<Departure> &dep) { roots.push_back(build(dep, 0, dep.size())); }
};

inline bool count(vector<int> *a, int v) {
    return binary_search(a->begin(), a->end(), v);
}

long long solve(
    int N, 
    int M,
    int W,
    vector<int> T,
    vector<int> X,
    vector<int> Y,
    vector<int> A,
    vector<int> B,
    vector<int> C,
    vector<int> L,
    vector<int> R
) {
    int start = clock();

    A.push_back(1e9 + 1);
    B.push_back(1e9 + 2);
    C.push_back(0);
    X.push_back(N - 1);
    Y.push_back(N);
    M++;

	vector<Departure> trains(M);
    for (int i = 0; i < M; i++)
        trains[i] = {i, X[i], A[i]};

    vector<variant<Meal, Arrival>> events;
    for (int i = 0; i < M; i++)
        events.push_back(Arrival {B[i], i});
    for (int i = 0; i < W; i++)
        events.push_back(Meal {L[i], R[i] + 1});

    sort(trains.begin(), trains.end(), [](const auto &a, const auto &b) { return a.time_start < b.time_start; });
    sort(events.begin(), events.end(), [](const auto &a, const auto &b) {
        int time_a, time_b;
        
        if (holds_alternative<Meal>(a))
            time_a = get<Meal>(a).l;
        else
            time_a = get<Arrival>(a).time;
        
        if (holds_alternative<Meal>(b))
            time_b = get<Meal>(b).l;
        else
            time_b = get<Arrival>(b).time;

        return time_a > time_b;
    });

    SegTree segtree(trains);
    vector<int> roots(M);

    for (auto event: events) {
        if (holds_alternative<Meal>(event)) {
            Meal meal = get<Meal>(event);
            segtree.add_meal(meal.r);
        } else {
            Arrival arrival = get<Arrival>(event);
            roots[arrival.idx] = segtree.get_curr_root();
        }
    }
    

    priority_queue<
        tuple<long long, SegTree::Node*, int>,
        vector<tuple<long long, SegTree::Node*, int>>,
        greater<tuple<long long, SegTree::Node*, int>>
    > q;

    q.emplace(0, segtree.roots.back(), 0);

    //segtree.debug(segtree.get_curr_root());

    while (!q.empty()) {
        auto [d, node, curr] = q.top(); q.pop();
        
        //cerr << d << " " << node << " " << curr << endl;
        
        if (curr == N) return d;
        if (node->visited.count(curr)) continue;
        node->visited.insert(curr);
    
        if (!count(node->valid, curr)) continue;

        if (!node->lc) {
            int idx = node->dep.idx;
            long long cost = T[curr] * node->sum + C[idx];
           
            if (Y[idx] == N) q.emplace(d + cost, nullptr, N);
            for (auto [nn, w]: segtree.get_continuation(B[idx], segtree.roots[roots[idx]])) {
                q.emplace(d + cost + w * T[curr], nn, Y[idx]);
            }
        } else {
            q.emplace(d, node->lc, curr);
            q.emplace(d + T[curr] * node->lc->sum, node->rc, curr);
        }
    }

    return -1;
}

Compilation message (stderr)

train.cpp: In function 'long long int solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:112:9: warning: unused variable 'start' [-Wunused-variable]
  112 |     int start = clock();
      |         ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60