Language: C++

#include "./toolkitA/scripts/output_checker_class.cpp"
#include <bits/stdc++.h>

#define range(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, b) for (int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x) cerr << #x << " = " << (x) << endl;

using namespace std;
using namespace std::chrono;

template<typename X, typename T>
auto vectors(X x, T a) {
    return vector<T>(x, a);
}

template<typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
    auto cont = vectors(y, z, zs...);
    return vector<decltype(cont)>(x, cont);
}

template<typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
    rep(i, v.size()) { os << v[i] << (i == v.size() - 1 ? "" : " "); }
    return os;
}

template<typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &x : v) { is >> x; }
    return is;
}

#define MAX_LV 400
#define WS 5
#define WH 1

const short INFS = 5000;
const short MAX_V = 400;
const short MAX_T = 10000;

typedef vector<short> vs;
typedef vector<vector<short>> vvs;

class WarshallFloyd {
    short V;
    vvs prev;

public:
    vector<int> ans;
    vvs m;

    WarshallFloyd() : V(MAX_V), prev(vvs(V, vs(V))), m(vvs(V, vs(V, INFS))) {
        rep(i, V) m[i][i] = 0;
        rep(i, V) rep(j, V) prev[i][j] = i;
    }

    void solve() {
        rep(k, V) {
            rep(i, V) {
                rep(j, V) {
                    if (m[i][j] > m[i][k] + m[k][j]) {
                        m[i][j] = m[i][k] + m[k][j];
                        prev[i][j] = prev[k][j];
                    }
                }
            }
        }
        rep(i, V) m[i][i] = 1; // $BBT5!$9$k$H;~9o(B +1
    }

    void outputPath(vs &move_ord, bool save = false) {
        vector<vvs> s_path(V, vvs(V)); // s_path[i][j] = i->j $B$N:GC;%3%9%H(Bpath
        rep(s, V) {
            rep(g, V) {
                for (int cur = g; cur != s; cur = prev[s][cur])
                    s_path[g][s].emplace_back(cur);
                s_path[g][s].emplace_back(s);
            }
        }
        reverse(all(move_ord));

        vs path;
        for (int i = move_ord.size() - 1; i > 0; i--) {
            short from = move_ord[i], to = move_ord[i - 1];
            if (s_path[from][to].size() == 1) {
                path.emplace_back(s_path[from][to][0]);
            } else {
                rep(j, s_path[from][to].size() - (i == 1 ? 0 : 1)) {
                    path.emplace_back(s_path[from][to][j]);
                    // printf("%d ", s_path[from][to][j]);
                }
            }
        }

        short need = MAX_T;
        rep(i, path.size() - 1) {
            short from = path[i], to = path[i + 1];
            if (from == to) {
                need--;
                if (save)
                    ans.emplace_back(-1);
                else
                    printf("-1\n");
            } else {
                need -= m[from][to];
                rep(_, m[from][to]) {
                    if (save)
                        ans.emplace_back(to + 1);
                    else
                        printf("%d\n", to + 1);
                }
            }
        }
        assert(need >= 0);
        while (need-- > 0) {
            if (save)
                ans.emplace_back(-1);
            else
                printf("-1\n");
        }
    }
};

class Order {
    template<typename T>
    class CumulativeSum {
        vector<T> a;

    public:
        void init(vector<T> &x) {
            a = vector<T>(x.size() + 1, 0);
            rep(i, x.size()) { a[i + 1] = a[i] + x[i]; }
        }

        T get(int l, int r) { // [l, r]$B$N6h4V$N9g7W$r5a$a$k(B
            return a[r + 1] - a[l];
        }

        T operator[](const int i) const { return a[i]; }
    };

    vs v;
    CumulativeSum<long long> sum, sqsum;

public:
    Order(vector<long long> &x) {
        v = vs(x.size());
        rep(i, x.size()) v[i] = static_cast<short>(x[i]);

        sum.init(x);
        for (auto &i : x) i *= i;
        sqsum.init(x);
    }

    long long getScore(short s, short e) { // [s, e]
        // rep(i,v.size()) cout << v[i] << ' '; cout << endl;
        auto low_it = lower_bound(all(v), s);
        auto up_it = upper_bound(all(v), e);

        short low_idx = distance(v.begin(), low_it);
        short up_idx = distance(v.begin(), up_it) - 1;

        long long dis = up_idx - low_idx + 1;
        if (dis < 0) return 0;
        return 100000000LL * dis - e * e * dis + e * sum.get(low_idx, up_idx) -
               sqsum.get(low_idx, up_idx);
    }
};

class Christofides {
    class Edge {
    public:
        short cost, from, to;

        Edge(short cost, short from, short to)
                : cost(cost), from(from), to(to) {}

        bool operator<(const Edge &right) const { return cost < right.cost; }

        bool operator>(const Edge &right) const { return cost > right.cost; }
    };

    vvs m;
    vs press; // press[i] := i $BHVL\$ND:E@$r05=L$7$?7k2L$ND:E@HV9f(B


    vvs prim(const vs &v) {
        int n = v.size();

        vector<bool> visited(n);
        visited[press[v[0]]] = true;

        priority_queue<Edge, vector<Edge>, greater<Edge>> q;
        for (auto p : v) { q.push({m[v[0]][p], v[0], p}); }

        vvs res(n);
        while (not q.empty()) {
            Edge u = q.top();
            q.pop();
            if (visited[press[u.to]]) continue;
            visited[press[u.to]] = true;
            res[press[u.from]].emplace_back(press[u.to]);
            res[press[u.to]].emplace_back(press[u.from]);
            for (auto to : v) {
                if (not visited[press[to]]) q.push({m[u.to][to], u.to, to});
            }
        }
        return res;
    }

    vector<pair<int, int>> gabowEdmonds(const vector<vector<int>> &graph) {
        int n = graph.size();
        vector<vector<pair<int, int>>> g(n + 1);
        vector<pair<int, int>> edges;
        int cnt = n + 1;
        for (int i = 0; i < n; i++) {
            for (auto to : graph[i]) {
                if (i < to) {
                    g[to + 1].emplace_back(i + 1, cnt);
                    g[i + 1].emplace_back(to + 1, cnt++);
                    edges.emplace_back(i + 1, to + 1);
                }
            }
        }

        vector<int> mate(n + 1, 0), label(n + 1, -1), first(n + 1, 0);
        queue<int> q;

        // first$B$NCY1dI>2A(B
        function<int(int)> eval_first = [&](int x) {
            if (label[first[x]] < 0) return first[x];
            first[x] = eval_first(first[x]);
            return first[x];
        };

        function<void(int, int)> rematch = [&](int v, int w) {
            int t = mate[v];
            mate[v] = w;
            if (mate[t] != v) return;

            if (label[v] <= n) {
                mate[t] = label[v];
                rematch(label[v], t);
            } else {
                int x, y;
                tie(x, y) = edges[label[v] - n - 1];
                rematch(x, y);
                rematch(y, x);
            }
        };

        function<void(int, int, int)> assignLabel = [&](int x, int y, int num) {
            int r = eval_first(x);
            int s = eval_first(y);
            if (r == s) return;

            label[r] = -num;
            label[s] = -num;
            int join = 0;
            while (true) {
                if (s != 0) swap(r, s);
                r = eval_first(label[mate[r]]);
                if (label[r] == -num) {
                    join = r;
                    break;
                }
                label[r] = -num;
            }

            int v = first[x];
            while (v != join) {
                q.emplace(v);
                label[v] = num;
                first[v] = join;
                v = first[label[mate[v]]];
            }
            v = first[y];
            while (v != join) {
                q.emplace(v);
                label[v] = num;
                first[v] = join;
                v = first[label[mate[v]]];
            }
            return;
        };

        function<bool(int)> augment_check = [&](int u) {
            first[u] = label[u] = 0;
            q.emplace(u);
            while (not q.empty()) {
                int x = q.front();
                q.pop();
                for (auto e : g[x]) {
                    int y = e.first;
                    if (mate[y] == 0 and y != u) {
                        mate[y] = x;
                        rematch(x, y);
                        return true;
                    } else if (label[y] >= 0) {
                        assignLabel(x, y, e.second);
                    } else if (label[mate[y]] < 0) {
                        label[mate[y]] = x;
                        first[mate[y]] = y;
                        q.emplace(mate[y]);
                    }
                }
            }
            return false;
        };

        for (int i = 1; i <= n; i++) {
            q = queue<int>();
            if (mate[i] != 0) continue;
            if (augment_check(i)) fill(label.begin(), label.end(), -1);
        }

        vector<pair<int, int>> ans;
        for (int i = 1; i <= n; i++) {
            if (i < mate[i]) ans.emplace_back(i - 1, mate[i] - 1);
        }
        return ans;
    }

    void visit(const vector<vector<Edge>> &g, vector<vector<short>> &adj, int s,
               vector<short> &path) {
        for (auto &e : g[s])
            if (adj[e.from][e.to]) {
                --adj[e.from][e.to];
                --adj[e.to][e.from];
                visit(g, adj, e.to, path);
            }
        path.push_back(s);
    }

    bool eulerPath(const vector<vector<Edge>> &g, int s, vector<short> &path) {
        int n = g.size();
        int odd = 0, m = 0;
        rep(i, n) {
            if (g[i].size() % 2 == 1) ++odd;
            m += g[i].size();
        }
        m /= 2;
        if (odd == 0 || (odd == 2 && g[s].size() % 2 == 1)) {
            vector<vector<short>> adj(n, vector<short>(n));
            rep(u, n) for (auto e : g[u])++adj[e.from][e.to];
            path.clear();
            visit(g, adj, s, path);
            reverse(all(path));
            return path.size() == m + 1;
        }
        return false;
    }

public:
    Christofides() {}

    void setShortestPath(vvs &m) {
        this->m = m;
    }

    vs solve(vs &v) { // $B%O%_%k%H%sJDO)$rJV$9(B
        short n = v.size();
        press = vs(MAX_V);
        rep(i, n) { press[v[i]] = i; }

        vvs tree = prim(v);
        vs degree(n, 0);
        rep(i, n) {
            for (auto to : tree[i]) { degree[to]++; }
        }

        vector<short> odd_v;
        rep(i, n) if (degree[i] % 2) odd_v.emplace_back(i);

        vector<vector<int>> subGraph(n);
        for (auto i : odd_v) {
            for (auto j : odd_v) {
                if (i == j) continue;
                subGraph[i].emplace_back(j);
            }
        }

        auto matchedEdge = gabowEdmonds(subGraph);
        for (auto &edge : matchedEdge) {
            tree[edge.first].emplace_back(edge.second);
            tree[edge.second].emplace_back(edge.first);
        }

        vector<vector<Edge>> h(n);
        rep(i, n) {
            for (auto to : tree[i]) {
                h[i].emplace_back(Edge{m[i][to], (short) i, (short) to});
            }
        }

        vs path;
        assert(eulerPath(h, 0, path) && "[*] Not found euler path");

        vs res;
        for (auto i : path) res.emplace_back(v[i]);
        return res;
    }
};

class Solver {
public:
    Christofides christofides;
    WarshallFloyd w;
    vector<Order> ord;
    vs tord; // tord[i] := $B;~9o(B t $B$KM?$($i$l$?%*!<%@!<(B
    Solver() : tord(MAX_T, -1) {}

    void init() {
        w = WarshallFloyd();
        ord.clear();
        fill(all(tord), -1);
    }

    void read() {
        short V, e;
        scanf("%hd%hd", &V, &e);

        rep(i, e) {
            short a, b, c;
            scanf("%hd%hd%hd", &a, &b, &c);
            a--;
            b--;
            w.m[a][b] = w.m[b][a] = c;
        }

        short t;
        scanf("%hd", &t);

        vector<vector<long long>> v(V);
        rep(i, t) {
            short n;
            scanf("%hd", &n);
            if (n) {
                short a;
                scanf("%*hd%hd", &a);
                a--;
                v[a].emplace_back(i);
                tord[i] = a;
            }
        }

        rep(i, V) { ord.emplace_back(Order(v[i])); }
        prepare();
    }

    void fread(char *name) {
        FILE *fp = fopen(name, "r");
        short V, e;
        fscanf(fp, "%hd%hd", &V, &e);

        rep(i, e) {
            short a, b, c;
            fscanf(fp, "%hd%hd%hd", &a, &b, &c);
            a--;
            b--;
            w.m[a][b] = w.m[b][a] = c;
        }

        short t;
        fscanf(fp, "%hd", &t);

        vector<vector<long long>> v(V);
        rep(i, t) {
            short n;
            fscanf(fp, "%hd", &n);
            if (n) {
                short a;
                fscanf(fp, "%*hd%hd", &a);
                a--;
                v[a].emplace_back(i);
                tord[i] = a;
            }
        }
        fclose(fp);

        rep(i, V) { ord.emplace_back(Order(v[i])); }
        prepare();
    }

    void prepare() {
        w.solve();
        christofides.setShortestPath(w.m);
    }

    vector<short> getOrders(short past, short current) {
        vector<short> res;
        range(i, past, current + 1) {
            if (tord[i] != -1) res.emplace_back(tord[i]);
        }
        return res;
    }

    pair<short, vs> delivery(vs &orders) {
        vs p;
        if (orders.size() == 1) {
            p = vs{orders.front(), 0};
        } else {
            orders.emplace_back(0);
            sort(all(orders));
            orders.erase(unique(all(orders)), orders.end());

            p = christofides.solve(orders);
            p.erase(p.begin()); // スタート地点は常に 0 のため，パスのスタートの 0 を消す
        }

        short delivery_time = w.m[0][p[0]];
        rep(i,p.size()){
            delivery_time += w.m[p[i]][p[i + 1]];
        }

        return make_pair(delivery_time, p);
    }

    void solve(bool save = false) {
        vs path;
        short time = 0, past = 0;
        vs orders;
        while (time < MAX_T) {
            orders = getOrders(past, time);
            if (orders.empty()) {
                time++;
                path.emplace_back(0);
                continue;
            }

            past = time + 1;

            short delivery_time;
            vs p;
            tie(delivery_time, p) =
                    delivery(orders);
            if (time + delivery_time >= MAX_T) {
                while(time + delivery_time >= MAX_T and p.size() >= 2){
                    short b = p.size() - 1;
                    delivery_time -= w.m[p[b]][p[b - 1]];
                    p.pop_back();
                }
                for (auto &i : p) path.emplace_back(i);
                break;
            }
            time += delivery_time;
            for (auto &i : p) path.emplace_back(i);
        }

        w.outputPath(path, save);
    }
};

struct Result {
    long long score, time;
    int testcase;

    static bool score_comp(Result &a, Result &b) { return a.score < b.score; }

    static bool time_comp(Result &a, Result &b) { return a.time < b.time; }
};

std::mutex mtx_;
vector<Result> res;
string progress = "                    ";

void addRes(Result result) {
    std::lock_guard<std::mutex> lock(mtx_);
    res.emplace_back(result);
}

void _getresult(int a, int b) {

    char name[126];
    Solver s;
    range(i, a, b) {
        auto start_time = high_resolution_clock::now();

        s.init();
        sprintf(name, "testcases/testcase-%d.in", i);

        s.fread(name);
        s.solve(true);

        auto dif = high_resolution_clock::now() - start_time;
        auto cal_time = duration_cast<milliseconds>(dif).count();

        addRes(Result{calScore(name, s.w.ans), cal_time, i});

        rep(j, res.size() / 5) progress[j] = '=';
        cerr << "\r" << '[' << progress << ']' << "   " << res.size() << "/100";
    }
}

inline void output(string tag, Result &r) {
    fprintf(stderr, "%s: %3d  %12lld  %5lldmsec\n", tag.c_str(), r.testcase,
            r.score, r.time);
}

void getResult() {
    //vector<int> s = {0, 1};
    vector<int> s = {0, 25, 50, 75, 100};
    // vector<int> s = {0,50,100};
    vector<thread> threads;
    rep(i, s.size() - 1) {
        threads.emplace_back(thread(_getresult, s[i], s[i + 1]));
    }
    for (auto &t : threads) t.join();
    cerr << endl;

    cerr << "Score" << endl;
    sort(all(res), Result::score_comp);
    output("max", res.back());
    output("min", res.front());
    output("mid", res[res.size() / 2]);
    fprintf(stderr, "ave:  __  %12lld\n",
            accumulate(all(res), 0LL, [](long long &b, Result &x) {
                return b + x.score;
            }) / 100);

    cerr << endl << "Time" << endl;
    sort(all(res), Result::time_comp);
    output("max", res.back());
    output("min", res.front());
    output("mid", res[res.size() / 2]);
    fprintf(stderr, "ave:  %12lldmsec\n",
            accumulate(all(res), 0LL, [](long long &b, Result &x) {
                return b + x.time;
            }) / 100);
}

signed main() {
    // vector<long long> a = {2,5,7,10,11,23};
    // Order od(a);
    // od.getScore(5,11);

    //getResult();
    //return 0;
    Solver s;
    s.read();
    //s.init();
    s.solve(true);
    for(auto& i : s.w.ans){
        cout << i << endl;
    }
    //cerr << calScore("testcases/testcase-0.in", s.w.ans) << endl;
}


Compiler output:
a.cc:1:10: fatal error: ./toolkitA/scripts/output_checker_class.cpp: No such file or directory
    1 | #include "./toolkitA/scripts/output_checker_class.cpp"
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.