Submission #1036757

#TimeUsernameProblemLanguageResultExecution timeMemory
1036757LaviniaTornaghiTrain (APIO24_train)C++17
0 / 100
150 ms111944 KiB
#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; } vector<pair<Node*, long long>> get_continuation(int r, Node *node, long long acc = 0) { if (!node->lc) { if (node->ma_time >= r) return {{node, acc}}; else return {}; } if (node->lc->ma_time >= r) { vector<pair<Node*, long long>> c = get_continuation(r, node->lc, acc); c.emplace_back(node->rc, acc + node->lc->sum); return c; } else { return get_continuation(r, node->rc, acc + node->lc->sum); } }; 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; q.emplace(0, segtree.roots.back(), 0); //segtree.debug(segtree.get_curr_root()); while (!q.empty()) { auto [d, node, curr] = q.top(); q.pop(); //cerr << d << " " << node << " " << curr << endl; if (!count(node->valid, curr)) continue; if (node->visited.count(curr)) continue; if (curr == N) return d; node->visited.insert(curr); if (!node->lc) { int idx = node->dep.idx; long long cost = T[curr] * node->sum + C[idx]; if (Y[idx] == N) q.emplace(d + cost, nullptr, N); for (auto [nn, w]: segtree.get_continuation(B[idx], segtree.roots[roots[idx]])) { q.emplace(d + cost + w * T[curr], nn, Y[idx]); } } else { q.emplace(d, node->lc, curr); q.emplace(d + T[curr] * node->lc->sum, node->rc, curr); } } return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...