Submission #703445

#	Time	Username	Problem	Language	Result	Execution time	Memory
703445		KoD	한자 끝말잇기 (JOI14_kanji)	C++17	0 / 100	468 ms	262144 KiB

Anna

#include "Annalib.h"

#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
    using namespace std;
    using ll = long long;
    using ull = unsigned long long;
    constexpr ll inf = numeric_limits<ll>::max() / 2;

    vector use(M, true);
    for (int i = 0; i < K; ++i) {
        use[U[i]] = false;
    }
    vector d(N, vector(N, inf));
    for (int i = 0; i < N; ++i) {
        d[i][i] = 0;
    }
    for (int i = 0; i < M; ++i) {
        if (use[i]) {
            d[A[i]][B[i]] = C[i];
        }
    }
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    map<int, vector<int>> g = {};
    {
        vector<int> v(Q);
        iota(begin(v), end(v), 0);
        g.emplace(-1, move(v));
    }
    ull send = 0, coeff = 1;
    for (int k = 0; k < K; ++k) {
        map<int, vector<int>> g2 = {};
        for (const auto& [j, v] : g) {
            if (j == -1) {
                for (const int i : v) {
                    if (d[S[i]][T[i]] - d[S[i]][A[U[k]]] - d[B[U[k]]][T[i]] <= C[U[k]]) {
                        send += coeff;
                        g2[j].push_back(i);
                    } else {
                        g2[k].push_back(i);
                    }
                }
            } else {
                for (const int i : v) {
                    if (d[B[U[j]]][T[i]] - d[B[U[k]]][T[i]] <= C[U[k]] - C[U[j]]) {
                        send += coeff;
                        g2[j].push_back(i);
                    } else {
                        g2[k].push_back(i);
                    }
                }
            }
            coeff *= v.size() + 1;
        }
        g = move(g2);
    }

    for (int i = 0; i < 64; ++i) {
        Tap(send >> i & 1);
    }
}

Bruno

#include "Brunolib.h"

#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
    using namespace std;
    using ll = long long;
    using ull = unsigned long long;
    constexpr ll inf = numeric_limits<ll>::max() / 2;

    vector use(M, true);
    for (int i = 0; i < K; ++i) {
        use[U[i]] = false;
    }
    vector d(N, vector(N, inf));
    vector adj(N, vector(N, -1));
    for (int i = 0; i < N; ++i) {
        d[i][i] = 0;
    }
    for (int i = 0; i < M; ++i) {
        if (use[i]) {
            d[A[i]][B[i]] = C[i];
            adj[A[i]][B[i]] = i;
        }
    }
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    vector rev(N, vector(N, -1));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                if (adj[k][j] != -1 and d[i][j] == d[i][k] + d[k][j]) {
                    rev[i][j] = adj[k][j];
                }
            }
        }
    }

    ull receive = 0;
    for (int i = 0; i < L; ++i) {
        receive |= (ull)X[i] << i;
    }
    map<int, vector<int>> g = {};
    {
        vector<int> v(Q);
        iota(begin(v), end(v), 0);
        g.emplace(-1, move(v));
    }
    for (int k = 0; k < K; ++k) {
        map<int, vector<int>> g2 = {};
        for (const auto& [j, v] : g) {
            vector<pair<ll, int>> v2;
            if (j == -1) {
                for (const int i : v) {
                    v2.emplace_back(d[S[i]][T[i]] - d[S[i]][A[U[k]]] - d[B[U[k]]][T[i]], i);
                }
            } else {
                for (const int i : v) {
                    v2.emplace_back(d[B[U[j]]][T[i]] - d[B[U[k]]][T[i]] <= C[U[k]] - C[U[j]], i);
                }
            }
            sort(begin(v2), end(v2));
            const int n = (int)v.size();
            const int m = receive % (n + 1);
            receive /= n + 1;
            for (int i = 0; i < m; ++i) {
                g2[j].push_back(v2[i].second);
            }
            for (int i = m; i < n; ++i) {
                g2[k].push_back(v2[i].second);
            }
        }
        g = move(g2);
    }
    
    vector<int> type(Q);
    for (const auto& [j, v] : g) {
        for (const int i : v) {
            type[i] = j;
        }
    }
    for (int i = 0; i < Q; ++i) {
        vector<int> ans;
        const auto add = [&](const int u, int v) {
            while (v != u) {
                const int e = rev[u][v];
                ans.push_back(e);
                v = A[e];
            }
        };
        if (const int j = type[i]; j == -1) {
            add(S[i], T[i]);
        } else {
            add(B[U[j]], T[i]);
            ans.push_back(U[j]);
            add(S[i], A[U[j]]);
        }
        reverse(begin(ans), end(ans));
        for (const int j : ans) {
            Answer(j);
        }
        Answer(-1);
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 8
• Subtask 4: 0 / 40
• Subtask 5: 0 / 20