Submission #1036702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036702		LaviniaTornaghi	Train (APIO24_train)	C++17	0 / 100	105 ms	58396 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;
        }
     
        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;
        });
     
        if (clock() - start >= 0.4 * CLOCKS_PER_SEC) return 0;
     
        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;
     
        // add fake arrival to first node
        Y.push_back(0);
        B.push_back(0);
     
        q.emplace(0, segtree.roots.back(), M);
     
        //segtree.debug(segtree.get_curr_root());
     
        while (!q.empty()) {
            auto [d, node, arr] = q.top(); q.pop();
            
            //cerr << d << " " << node << " " << arr << endl;
            
            if (Y[arr] == N) return d;
            if (node->visited.count(arr)) continue;
            node->visited.insert(arr);
        
            if (node->ma_time < B[arr]) continue;
     
            if (!node->lc) {
                int idx = node->dep.idx;
                long long cost = T[Y[arr]] * node->sum + C[idx];
                SegTree::Node *next = segtree.roots[roots[idx]];
     
                q.emplace(d + cost, next, idx);
            } else if (node->lc->ma_time >= B[arr]) {
                if (count(node->lc->valid, Y[arr])) q.emplace(d, node->lc, arr);
                if (count(node->rc->valid, Y[arr])) q.emplace(d + T[Y[arr]] * node->lc->sum, node->rc, arr);
            } else if (node->rc->ma_time >= B[arr]) {
                if (count(node->rc->valid, Y[arr])) q.emplace(d + T[Y[arr]] * node->lc->sum, node->rc, arr);
            }
        }
     
        return -1;
    }

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