Submission #259171

#	Time	Username	Problem	Language	Result	Execution time	Memory
259171		imeimi2000	한자 끝말잇기 (JOI14_kanji)	C++17	100 / 100	216 ms	27360 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

static void dijkstra(vector<pll> edge[], llong dist[], int prev[], int s) {
    priority_queue<pll> pq;
    pq.emplace(dist[s] = 0, s);
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        d = -d;
        if (dist[x] != d) continue;
        for (auto [i, c] : edge[x]) {
            if (d + c < dist[i]) pq.emplace(-(dist[i] = d + c), i), prev[i] = x;
        }
    }
}

const static llong inf = 4e18;
static vector<pll> edge[300];
static llong distK[6][300], distQ[60][300];
static int par[300], a;

static llong get_dist(int i, int x, int k) {
    if (k) return distQ[i][a] + distK[k][x];
    return distQ[i][x];
}

void Anna(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[]) {
    a = A[U[0]];
    for (int i = 0; i < m; ++i) {
        bool in = 0;
        for (int j = 0; j < k; ++j) if (i == U[j]) in = 1;
        if (!in) edge[A[i]].emplace_back(B[i], C[i]);
    }
    memset(distQ, 0x3f, sizeof(distQ));
    for (int i = 0; i < q; ++i) {
        dijkstra(edge, distQ[i], par, S[i]);
    }
    memset(distK, 0x3f, sizeof(distK));
    for (int i = 1; i <= k; ++i) {
        dijkstra(edge, distK[i], par, B[U[i - 1]]);
        for (int j = 0; j < n; ++j) distK[i][j] += C[U[i - 1]];
    }
    vector<int> G[6];
    for (int i = 0; i < q; ++i) G[0].push_back(i);
    unsigned long long ret = 0;
    vector<unsigned> mul, add;
    for (int w = 1; w <= k; ++w) {
        for (int i = 0; i < w; ++i) {
            vector<int> O, N;
            for (int g : G[i]) {
                if (distQ[g][a] >= inf || distK[w][T[g]] >= inf) O.push_back(g);
                else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                else (get_dist(g, T[g], i) <= get_dist(g, T[g], w) ? O : N).push_back(g);
            }
            mul.push_back(G[i].size() + 1u);
            add.push_back(O.size());
            G[i] = O;
            for (int j : N) G[w].push_back(j);
        }
    }
    for (int i = mul.size(); i--; ) ret = ret * mul[i] + add[i];
    while (ret) Tap(ret & 1u), ret >>= 1;
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

static void dijkstra(vector<pll> edge[], llong dist[], int prev[], int s) {
    priority_queue<pll> pq;
    pq.emplace(dist[s] = 0, s);
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        d = -d;
        if (dist[x] != d) continue;
        for (auto [i, c] : edge[x]) {
            if (d + c < dist[i]) pq.emplace(-(dist[i] = d + c), i), prev[i] = x;
        }
    }
}

const static llong inf = 4e18;
static vector<pll> edge[300];
static llong distK[6][300], distQ[60][300];
static int parK[6][300], parQ[60][300], a;

static llong get_dist(int i, int x, int k) {
    if (k) return distQ[i][a] + distK[k][x];
    return distQ[i][x];
}

void Bruno(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[], int l, int V[]) {
    unsigned long long ret = 0;
    while (l--) ret = ret << 1 | unsigned(V[l]);
    a = A[U[0]];
    map<pll, int> idx;
    for (int i = 0; i < m; ++i) {
        idx[pll(A[i], B[i])] = i;
        if (C[i] != -1) edge[A[i]].emplace_back(B[i], C[i]);
    }
    memset(distQ, 0x3f, sizeof(distQ));
    for (int i = 0; i < q; ++i) {
        dijkstra(edge, distQ[i], parQ[i], S[i]);
    }
    memset(distK, 0x3f, sizeof(distK));
    for (int i = 1; i <= k; ++i) {
        dijkstra(edge, distK[i], parK[i], B[U[i - 1]]);
    }
    vector<int> G[6];
    for (int i = 0; i < q; ++i) G[0].push_back(i);
    for (int w = 1; w <= k; ++w) {
        for (int i = 0; i < w; ++i) {
            int cnt = ret % (G[i].size() + 1u);
            ret /= G[i].size() + 1u;
            vector<int> nG, O, N;
            for (int g : G[i]) {
                if (distQ[g][a] >= inf || distK[w][T[g]] >= inf) O.push_back(g), --cnt;
                else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                else nG.push_back(g);
            }
            sort(nG.begin(), nG.end(), [&](int a, int b) {
                return get_dist(a, T[a], i) - get_dist(a, T[a], w) < get_dist(b, T[b], i) - get_dist(b, T[b], w);
            });
            for (int j = 0; j < int(nG.size()); ++j) (j < cnt ? O : N).push_back(nG[j]);
            G[i] = O;
            for (int j : N) G[w].push_back(j);
        }
    }
    int res[60];
    for (int i = 0; i <= k; ++i) for (int j : G[i]) res[j] = i;
    for (int i = 0; i < q; ++i) {
        int x = T[i];
        vector<int> path;
        if (res[i]) {
            for (; x != B[U[res[i] - 1]]; x = parK[res[i]][x]) path.push_back(idx[pll(parK[res[i]][x], x)]);
            path.push_back(U[res[i] - 1]);
            x = a;
        }
        for (; x != S[i]; x = parQ[i][x]) path.push_back(idx[pll(parQ[i][x], x)]);
        for (int j = path.size(); j--; ) Answer(path[j]);
        Answer(-1);
    }
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, int, int*, int*, llong*, int, int*, int*, int, int*)':
Anna.cpp:56:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, int*, int*, llong*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:57:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~

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