oj.uz

Submission #1036678

# Submission time Handle Problem Language Result Execution time Memory
1036678 2024-07-27T15:25:18 Z LaviniaTornaghi Train (APIO24_train) C++17
10 / 100
 1000 ms 367816 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.8 * 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 1116 KB Correct.
2 Correct 1 ms 960 KB Correct.
3 Correct 2 ms 988 KB Correct.
4 Correct 3 ms 1236 KB Correct.
5 Correct 0 ms 436 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 92 ms 56900 KB Correct.
2 Correct 105 ms 58148 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 8 ms 1728 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 150 ms 64164 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 192 ms 91812 KB Correct.
9 Correct 99 ms 57164 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 56900 KB Correct.
2 Correct 105 ms 58148 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 8 ms 1728 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 150 ms 64164 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 192 ms 91812 KB Correct.
9 Correct 99 ms 57164 KB Correct.
10 Correct 258 ms 289216 KB Correct.
11 Correct 361 ms 317352 KB Correct.
12 Correct 8 ms 1624 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Execution timed out 1108 ms 367816 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 1116 KB Correct.
2 Correct 1 ms 960 KB Correct.
3 Correct 2 ms 988 KB Correct.
4 Correct 3 ms 1236 KB Correct.
5 Correct 0 ms 436 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 92 ms 56900 KB Correct.
9 Correct 105 ms 58148 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 8 ms 1728 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 150 ms 64164 KB Correct.
14 Correct 1 ms 348 KB Correct.
15 Correct 192 ms 91812 KB Correct.
16 Correct 99 ms 57164 KB Correct.
17 Correct 258 ms 289216 KB Correct.
18 Correct 361 ms 317352 KB Correct.
19 Correct 8 ms 1624 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Execution timed out 1108 ms 367816 KB Time limit exceeded
22 Halted 0 ms 0 KB -