oj.uz

Submission #1036680

# Submission time Handle Problem Language Result Execution time Memory
1036680 2024-07-27T15:25:55 Z LaviniaTornaghi Train (APIO24_train) C++17
10 / 100
 1000 ms 367412 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;
        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 (!count(node->valid, 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];
            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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Correct.
2 Correct 1 ms 964 KB Correct.
3 Correct 1 ms 860 KB Correct.
4 Correct 2 ms 1236 KB Correct.
5 Correct 0 ms 348 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 87 ms 55748 KB Correct.
2 Correct 90 ms 56200 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 7 ms 1628 KB Correct.
5 Correct 0 ms 396 KB Correct.
6 Correct 120 ms 62760 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 140 ms 90288 KB Correct.
9 Correct 85 ms 55336 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 55748 KB Correct.
2 Correct 90 ms 56200 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 7 ms 1628 KB Correct.
5 Correct 0 ms 396 KB Correct.
6 Correct 120 ms 62760 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 140 ms 90288 KB Correct.
9 Correct 85 ms 55336 KB Correct.
10 Correct 232 ms 286912 KB Correct.
11 Correct 321 ms 314400 KB Correct.
12 Correct 7 ms 1624 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Execution timed out 1102 ms 367412 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 1112 KB Correct.
2 Correct 1 ms 964 KB Correct.
3 Correct 1 ms 860 KB Correct.
4 Correct 2 ms 1236 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 87 ms 55748 KB Correct.
9 Correct 90 ms 56200 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 7 ms 1628 KB Correct.
12 Correct 0 ms 396 KB Correct.
13 Correct 120 ms 62760 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Correct 140 ms 90288 KB Correct.
16 Correct 85 ms 55336 KB Correct.
17 Correct 232 ms 286912 KB Correct.
18 Correct 321 ms 314400 KB Correct.
19 Correct 7 ms 1624 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Execution timed out 1102 ms 367412 KB Time limit exceeded
22 Halted 0 ms 0 KB -