oj.uz

답안 #1036673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036673 2024-07-27T15:17:11 Z LaviniaTornaghi 은하철도 (APIO24_train) C++17
10 / 100
 1000 ms 398760 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;
        unordered_set<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 unordered_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 unordered_set<int>(*lc->valid);
            valid->merge(unordered_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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1628 KB Correct.
2 Correct 1 ms 1372 KB Correct.
3 Correct 2 ms 1492 KB Correct.
4 Correct 3 ms 1628 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

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 128060 KB Correct.
2 Correct 150 ms 139728 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 6 ms 1716 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 167 ms 120940 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 215 ms 113388 KB Correct.
9 Correct 148 ms 138980 KB Correct.

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 128060 KB Correct.
2 Correct 150 ms 139728 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 6 ms 1716 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 167 ms 120940 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 215 ms 113388 KB Correct.
9 Correct 148 ms 138980 KB Correct.
10 Correct 302 ms 360532 KB Correct.
11 Correct 537 ms 398760 KB Correct.
12 Correct 7 ms 1884 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Execution timed out 1050 ms 387012 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1628 KB Correct.
2 Correct 1 ms 1372 KB Correct.
3 Correct 2 ms 1492 KB Correct.
4 Correct 3 ms 1628 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 148 ms 128060 KB Correct.
9 Correct 150 ms 139728 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 6 ms 1716 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 167 ms 120940 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 215 ms 113388 KB Correct.
16 Correct 148 ms 138980 KB Correct.
17 Correct 302 ms 360532 KB Correct.
18 Correct 537 ms 398760 KB Correct.
19 Correct 7 ms 1884 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Execution timed out 1050 ms 387012 KB Time limit exceeded
22 Halted 0 ms 0 KB -