oj.uz

답안 #1036674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036674 2024-07-27T15:21:46 Z LaviniaTornaghi 은하철도 (APIO24_train) C++17
10 / 100
 1000 ms 373548 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
) {
    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 (!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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1116 KB Correct.
2 Correct 1 ms 860 KB Correct.
3 Correct 2 ms 1116 KB Correct.
4 Correct 2 ms 1116 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 57356 KB Correct.
2 Correct 95 ms 58408 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 7 ms 1716 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 121 ms 64268 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 147 ms 91948 KB Correct.
9 Correct 90 ms 57384 KB Correct.

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 57356 KB Correct.
2 Correct 95 ms 58408 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 7 ms 1716 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 121 ms 64268 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 147 ms 91948 KB Correct.
9 Correct 90 ms 57384 KB Correct.
10 Correct 236 ms 289316 KB Correct.
11 Correct 335 ms 317404 KB Correct.
12 Correct 7 ms 1628 KB Correct.
13 Correct 0 ms 436 KB Correct.
14 Execution timed out 1112 ms 373548 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1116 KB Correct.
2 Correct 1 ms 860 KB Correct.
3 Correct 2 ms 1116 KB Correct.
4 Correct 2 ms 1116 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 93 ms 57356 KB Correct.
9 Correct 95 ms 58408 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 7 ms 1716 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 121 ms 64268 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 147 ms 91948 KB Correct.
16 Correct 90 ms 57384 KB Correct.
17 Correct 236 ms 289316 KB Correct.
18 Correct 335 ms 317404 KB Correct.
19 Correct 7 ms 1628 KB Correct.
20 Correct 0 ms 436 KB Correct.
21 Execution timed out 1112 ms 373548 KB Time limit exceeded
22 Halted 0 ms 0 KB -