Submission #1308812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308812		elush	한자 끝말잇기 (JOI14_kanji)	C++20	80 / 100	143 ms	12144 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;

const ll infinity = 4e18;

vi Dijkstra(int start, vector<vii> &graph) {
    priority_queue<pii, vii, greater<pii>> pq;
    pq.push({0, start});
    int n = graph.size();
    vi dist(n, infinity);
    dist[start] = 0;
    while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();
        if (d > dist[node]) continue;
        for (auto [neighbor, w] : graph[node]) {
            if (d + w < dist[neighbor]) {
                pq.push({d + w, neighbor});
                dist[neighbor] = d + w;
            }
        }
    }
    return dist;
}

void Send(int j, int len) {
    while (len--) {
        Tap(j & 1);
        j >>= 1;
    }
}

void Anna(int n, int m, int a[], int b[], ll c[], int q, int s[], int t[], int k, int u[]) {
    vector<vii> graph(n), inv_graph(n);
    vi ok(m, 1);
    for (int i = 0; i < k; i++) ok[u[i]] = 0;
    for (int i = 0; i < m; i++) {
        if (ok[i]) {
            graph[a[i]].push_back({b[i], c[i]});
            inv_graph[b[i]].push_back({a[i], c[i]});
        }
    }
    vvi vals(15, {infinity});
    for (int i = 0; i < q; i++) {
        vi d1 = Dijkstra(s[i], graph);
        vi d2 = Dijkstra(t[i], inv_graph);
        vi d(k + 1);
        d[k] = d1[t[i]];
        for (int j = 0; j < k; j++) d[j] = min(d1[a[u[j]]] + d2[b[u[j]]], infinity);
        int ind = 0;
        for (int j = 0; j < k; j++) {
            for (int l = j + 1; l <= k; l++) {
                vals[ind++].push_back(d[l] - d[j]);
            }
        }
    }
    vi real(15);
    int ind = 0;
    for (int j = 0; j < k; j++) {
        for (int l = j + 1; l <= k; l++) {
            real[ind++] = c[u[j]] - (l == k ? 0 : c[u[l]]);
        }
    }
    for (int i = 0; i < (k + 1) * k / 2; i++) {
        sort(all(vals[i]));
        int j = lower_bound(all(vals[i]), real[i]) - vals[i].begin();
        Send(j, 6);
    }
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;

const ll infinity2 = 4e18;

pair<vi, vii> Dijkstra(int start, vector<vector<tuple<int, ll, int>>> &graph) {
    priority_queue<pii, vii, greater<pii>> pq;
    pq.push({0, start});
    int n = graph.size();
    vi dist(n, infinity2);
    vii prev(n, {-1, -1});
    dist[start] = 0;
    while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();
        if (d > dist[node]) continue;
        for (auto [neighbor, w, ind] : graph[node]) {
            if (d + w < dist[neighbor]) {
                pq.push({d + w, neighbor});
                dist[neighbor] = d + w;
                prev[neighbor] = {node, ind};
            }
        }
    }
    return {dist, prev};
}

int Read(int l, int r, vi &x) {
    int ans = 0;
    for (int i = r - 1; i >= l; i--) {
        ans = (ans << 1) + x[i];
    }
    return ans;
}

vi GetPath(int node, vii &prev) {
    vi ans;
    while (prev[node].first != -1) {
        ans.push_back(prev[node].second);
        node = prev[node].first;
    }
    reverse(all(ans));
    return ans;
}

void Bruno(int n, int m, int a[], int b[], ll c[], int q, int s[], int t[], int k, int u[], int L, int X[]) {
    vi x(L);
    for (int i = 0; i < L; i++) x[i] = X[i];
    vector<vector<tuple<int, ll, int>>> graph(n), inv_graph(n);
    vi ok(m, 1);
    for (int i = 0; i < k; i++) ok[u[i]] = 0;
    for (int i = 0; i < m; i++) {
        if (ok[i]) {
            graph[a[i]].push_back({b[i], c[i], i});
            inv_graph[b[i]].push_back({a[i], c[i], i});
        }
    }
    vvi vals(15, {infinity2});
    for (int i = 0; i < q; i++) {
        auto [d1, p1] = Dijkstra(s[i], graph);
        auto [d2, p2] = Dijkstra(t[i], inv_graph);
        vi d(k + 1);
        d[k] = d1[t[i]];
        for (int j = 0; j < k; j++) d[j] = min(d1[a[u[j]]] + d2[b[u[j]]], infinity2);
        int ind = 0;
        for (int j = 0; j < k; j++) {
            for (int l = j + 1; l <= k; l++) {
                vals[ind++].push_back(d[l] - d[j]);
            }
        }
    }
    vi real(15);
    for (int i = 0; i < (k + 1) * k / 2; i++) {
        sort(all(vals[i]));
        real[i] = vals[i][Read(6 * i, 6 * (i + 1), x)];
    }
    for (int i = 0; i < q; i++) {
        auto [d1, p1] = Dijkstra(s[i], graph);
        auto [d2, p2] = Dijkstra(t[i], inv_graph);
        vi d(k + 1);
        d[k] = d1[t[i]];
        for (int j = 0; j < k; j++) d[j] = min(d1[a[u[j]]] + d2[b[u[j]]], infinity2);
        int ind = 0;
        vi bad(k + 1);
        for (int j = 0; j < k; j++) {
            for (int l = j + 1; l <= k; l++) {
                if (real[ind++] <= d[l] - d[j]) bad[l] = 1;
                else bad[j] = 1;
            }
        }
        int j;
        for (j = 0; bad[j]; j++);
        vi path;
        if (j < k) {
            path = GetPath(a[u[j]], p1);
            path.push_back(u[j]);
            vi path2 = GetPath(b[u[j]], p2);
            reverse(all(path2));
            for (int y : path2) path.push_back(y);
        } else {
            path = GetPath(t[i], p1);
        }
        for (int y : path) Answer(y);
        Answer(-1);
    }
}

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