oj.uz

Submission #1036670

# Submission time Handle Problem Language Result Execution time Memory
1036670 2024-07-27T15:15:00 Z LaviniaTornaghi Train (APIO24_train) C++17
10 / 100
 1000 ms 375340 KB 
#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;
        set<int> *valid;
        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 set<int>;
            valid->insert(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 set<int>(*lc->valid);
            valid->merge(set<int>(*rc->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())); }
};

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
) {
    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;

    // 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->valid->count(Y[arr]) || node->ma_time < B[arr]) continue;

        if (!node->lc) {
            int idx = node->dep.idx;
            long long cost = T[Y[arr]] * node->sum + C[idx];
            assert(A[node->dep.idx] >= B[arr]);
            assert(node->valid->count(Y[arr]));
            SegTree::Node *next = segtree.roots[roots[idx]];

            q.emplace(d + cost, next, idx);
        } else if (node->lc->ma_time >= B[arr]) {
            if (node->lc->valid->count(Y[arr])) q.emplace(d, node->lc, arr);
            if (node->rc->valid->count(Y[arr])) q.emplace(d + T[Y[arr]] * node->lc->sum, node->rc, arr);
        } else if (node->rc->ma_time >= B[arr]) {
            if (node->rc->valid->count(Y[arr])) q.emplace(d + T[Y[arr]] * node->lc->sum, node->rc, arr);
        }
    }

    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Correct.
2 Correct 2 ms 1372 KB Correct.
3 Correct 2 ms 1336 KB Correct.
4 Correct 3 ms 1396 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 116516 KB Correct.
2 Correct 200 ms 129824 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 7 ms 1652 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 214 ms 105916 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 148 ms 76708 KB Correct.
9 Correct 191 ms 129576 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 116516 KB Correct.
2 Correct 200 ms 129824 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 7 ms 1652 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 214 ms 105916 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 148 ms 76708 KB Correct.
9 Correct 191 ms 129576 KB Correct.
10 Correct 350 ms 346404 KB Correct.
11 Correct 533 ms 370468 KB Correct.
12 Correct 9 ms 1628 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Execution timed out 1106 ms 375340 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Correct.
2 Correct 2 ms 1372 KB Correct.
3 Correct 2 ms 1336 KB Correct.
4 Correct 3 ms 1396 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 181 ms 116516 KB Correct.
9 Correct 200 ms 129824 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 7 ms 1652 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 214 ms 105916 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 148 ms 76708 KB Correct.
16 Correct 191 ms 129576 KB Correct.
17 Correct 350 ms 346404 KB Correct.
18 Correct 533 ms 370468 KB Correct.
19 Correct 9 ms 1628 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Execution timed out 1106 ms 375340 KB Time limit exceeded
22 Halted 0 ms 0 KB -