Language: C++

//
// ver 1.6
//

#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <cassert>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

#define PROBLEM_TYPE 'B'

using namespace std;

const int INF = 12345678;

class Action {
public:
    enum class Type {
        STAY,
        MOVE
    };

    Type type;
    int target;

    Action(Type type, int target = -1) : type(type), target(target) {}

    void output() {
        if (type == Type::STAY) {
            cout << -1 << endl;
        } else if (type == Type::MOVE) {
            cout << target + 1 << endl;
        }
    }
};

class Solver {
private:
    class Edge {
    public:
        int next;
        int distance;

        Edge(int next, int distance) : next(next), distance(distance) {}
    };

    class Node {
    public:
        int frequency = -1;
        vector<Edge> edges;

        void addEdge(int next, int distance) {
            edges.emplace_back(next, distance);
        }
    };

    class Order {
    public:
        int id;
        int destination;
        int orderedTurn;

        Order() {}
        Order(int id, int destination, int orderedTurn) : id(id), destination(destination), orderedTurn(orderedTurn) {}

        bool operator< (const Order &a) const {
            return id < a.id;
        }
    };

    int V, E;
    int turn;
    int maxTurn;
    int currentNode;
    vector<Node*> nodes;
    map<int, Order> orders;
    set<int> carry, stock;

    int distanceTable[400][400];
    deque<int> reservedRoute;

    int targetNode;
    int delay;

    int calcOrderScore(const Order &order, int currentTurn) {
        int passedTurn = currentTurn - order.orderedTurn;
        return maxTurn * maxTurn - passedTurn * passedTurn;
    }

    int calcRouteLength(deque<int> &route) {
        int length = 0;
        rep(i, route.size() - 1) {
            length += distanceTable[route[i]][route[i + 1]];
        }
        return length;
    }

    deque<int> calcRoute(const set<int> &carry, int start = 0, int goal = 0) {
        deque<int> route;
        route.push_back(start);
        route.push_back(goal);

        vector<Order> carriedOrders;
        for (auto orderId : carry) {
            carriedOrders.push_back(orders[orderId]);
        }
        sort(all(carriedOrders), [](Order &a, Order &b) {
            return a.orderedTurn < b.orderedTurn;
        });

        int routeLength = 0;
        set<int> visited;
        multimap<int, Order> ordersByCustomer;
        for (const auto &order : carriedOrders) {
            if (visited.find(order.destination) != visited.end()) continue;
            int minIdx = -1;
            int minDiff = INF;
            rep(i, route.size() - 1) {
                int diff = distanceTable[route[i]][order.destination]
                            + distanceTable[order.destination][route[i + 1]]
                            - distanceTable[route[i]][route[i + 1]];
                if (diff < minDiff) {
                    minDiff = diff;
                    minIdx = i;
                }
            }
            if (minIdx != -1 && routeLength + minDiff < 500) {
                route.insert(route.begin() + minIdx + 1, order.destination);
                visited.insert(order.destination);
                routeLength += minDiff;
                ordersByCustomer.insert(make_pair(order.destination, order));
            }
        }

        deque<int> path;

        path.push_front(0);
        rep (i, route.size() - 1) {
            auto tmpPath = calcPath(route[i], route[i + 1]);
            path.insert(path.end(), all(tmpPath));
        }

        auto calcPathScore = [&](const deque<int> &path) {
            long long score = 0;
            int extraTurn = 0;
            REP(i, 1, path.size() - 1) {
                extraTurn += distanceTable[path[i - 1]][path[i]];
                if (turn + extraTurn > maxTurn) break;
                auto its = ordersByCustomer.equal_range(path[i]);
                for (auto it = its.first; it != its.second; it++) {
                    score += calcOrderScore(it->second, turn + extraTurn);
                }
            }
            return score;
        };

        deque<int> reversedPath = path;
        reverse(all(reversedPath));

        long long straightScore = calcPathScore(path);
        long long reverseScore = calcPathScore(reversedPath);

        path.pop_front();
        reversedPath.pop_front();

        return straightScore > reverseScore ? path : reversedPath;
    }

    deque<int> calcRouteGreedy(set<int> carry, int start = 0, int goal = 0) {
        int now = currentNode;
        int currentTurn = turn;
        int cnt[400];
        memset(cnt, 0, sizeof(cnt));

        for (auto orderId : carry) {
            cnt[orders[orderId].destination]++;
        }

        deque<int> path;
        while (currentTurn < maxTurn && !carry.empty()) {
            int maxDest = -1;
            double maxRate = 0;
            for (auto orderId : carry) {
                int dest = orders[orderId].destination;
                int dist = distanceTable[now][dest];
                assert(dist);
                if (currentTurn + dist >= maxTurn) continue;
                double rate = (double) cnt[dest] / dist;
                if (rate > maxRate) {
                    maxRate = rate;
                    maxDest = dest;
                }
            }
            if (maxDest == -1) break;
            auto tmpPath = calcPath(now, maxDest);
            path.insert(path.end(), all(tmpPath));
            now = maxDest;
            currentTurn += distanceTable[now][maxDest];

            set<int> removeCarry;
            for (auto orderId : carry) {
                if (orders[orderId].destination == maxDest) {
                    removeCarry.insert(orderId);
                }
            }
            for (auto orderId : removeCarry) {
                carry.erase(orderId);
            }
        }
        auto tmpPath = calcPath(now, 0);
        path.insert(path.end(), all(tmpPath));

        return path;
    }

    deque<int> calcPath(int start, int goal) {
        int prev[400], dist[400];
        rep(i, V) {
            prev[i] = -1;
            dist[i] = INF;
        }
        priority_queue<pair<int, int>> q;
        q.push(make_pair(0, start));
        dist[start] = 0;

        while (!q.empty()) {
            auto pr = q.top(); q.pop();
            int nowDist = -pr.first;
            int nowNode = pr.second;
            if (nowDist > dist[nowNode]) continue;
            if (nowNode == goal) {
                break;
            }
            for (const auto &edge : nodes[nowNode]->edges) {
                int nextNode = edge.next;
                int nextDist = nowDist + edge.distance;
                if (nextDist >= dist[nextNode]) continue;
                dist[nextNode] = nextDist;
                prev[nextNode] = nowNode;
                q.push(make_pair(-nextDist, nextNode));
            }
        }

        deque<int> path;
        int nowNode = goal;
        while (nowNode != start) {
            path.push_front(nowNode);
            nowNode = prev[nowNode];
        }

        return path;
    }

public:
    bool finished;

    void initialize(char problemType) {
        cin >> V >> E;

        rep(_, V) {
            nodes.push_back(new Node());
        }

        rep(_, E) {
            int u, v, d;
            cin >> u >> v >> d;
            u--; v--;
            nodes[u]->addEdge(v, d);
            nodes[v]->addEdge(u, d);
        }

        if (problemType == 'B') {
            rep(i, V) {
                cin >> nodes[i]->frequency;
            }
        }

        cin >> maxTurn;

        turn = 0;
        currentNode = 0;
        delay = 0;

        rep(i, V) rep(j, V) distanceTable[i][j] = INF;
        rep(i, V) distanceTable[i][i] = 0;
        rep(i, V) {
            for (const auto &edge : nodes[i]->edges) {
                distanceTable[i][edge.next] = edge.distance;
            }
        }
        rep(k, V) rep(i, V) rep(j, V)
            distanceTable[i][j] = min(distanceTable[i][j], distanceTable[i][k] + distanceTable[k][j]);
    }

    void input1(char problemType) {
        int newN;
        cin >> newN;

        rep(_, newN) {
            int id, dst;
            cin >> id >> dst;
            dst--;
            orders[id] = Order(id, dst, turn);
            stock.insert(id);
        }

        if (problemType == 'A') {
            if (currentNode == 0) {
                carry.insert(all(stock));
                stock.clear();
            }
        } else {
            int putN;
            cin >> putN;

            rep(_, putN) {
                int id;
                cin >> id;
                carry.insert(id);
                stock.erase(id);
            }
        }
    }

    Action think() {
        if (delay > 0) {
            delay--;
            return Action(Action::Type::MOVE, targetNode);
        }

        if (!reservedRoute.empty()) {
            targetNode = reservedRoute[0];
            delay = distanceTable[currentNode][targetNode];
            currentNode = reservedRoute[0];
            reservedRoute.pop_front();
            return think();
        }

        assert(currentNode == 0);

        if (carry.empty()) {
            return Action(Action::Type::STAY);
        }

        reservedRoute = turn < maxTurn - 500 ? calcRoute(carry) : calcRouteGreedy(carry);

        return think();
    }

    void input2(char problemType) {
        if (problemType == 'A') {
            vector<int> achieveOrderIds;
            for (auto orderId : carry) {
                if (currentNode == orders[orderId].destination) {
                    achieveOrderIds.push_back(orderId);
                }
            }
            for (auto orderId : achieveOrderIds) {
                carry.erase(orderId);
            }
        } else {
            string verdict;
            cin >> verdict;

            if (verdict != "OK") {
                finished = true;
                return;
            }

            int achieveN;
            cin >> achieveN;

            rep(_, achieveN) {
                int id;
                cin >> id;
                carry.erase(id);
            }
        }
    }

    void finalizeTurn() {
        turn++;
        if (turn == maxTurn) finished = true;
    }
};

int main() {
    auto solver = Solver();

    solver.initialize(PROBLEM_TYPE);

    while (!solver.finished) {
        solver.input1(PROBLEM_TYPE);

        auto action = solver.think();
        action.output();

        solver.input2(PROBLEM_TYPE);

        solver.finalizeTurn();
    }

    return 0;
}


Compiler output:
a.cc: In member function 'std::deque<int> Solver::calcRoute(const std::set<int>&, int, int)':
a.cc:116:9: error: 'sort' was not declared in this scope; did you mean 'short'?
  116 |         sort(all(carriedOrders), [](Order &a, Order &b) {
      |         ^~~~
      |         short
a.cc:167:9: error: 'reverse' was not declared in this scope
  167 |         reverse(all(reversedPath));
      |         ^~~~~~~
a.cc: In member function 'std::deque<int> Solver::calcRouteGreedy(std::set<int>, int, int)':
a.cc:182:9: error: 'memset' was not declared in this scope
  182 |         memset(cnt, 0, sizeof(cnt));
      |         ^~~~~~
a.cc:14:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
   13 | #include <cassert>
  +++ |+#include <cstring>
   14 |