Submission #1309059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309059		elush	한자 끝말잇기 (JOI14_kanji)	C++20	100 / 100	529 ms	12116 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(ll j, ll 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]});
        }
    }
    vi bits = {0, 6, 10, 14, 16, 18};
    vi opt(q);
    for (int it = 1; it <= k; it++) {
        vvi vals(it, {infinity});
        vi real(it);
        for (int i = 0; i < it; i++) {
            real[i] = c[u[i]] - (it == k ? 0 : c[u[it]]);
        }
        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);
            vals[opt[i]].push_back(d[it] - d[opt[i]]);
            if (real[opt[i]] > d[it] - d[opt[i]]) opt[i] = it;
        }
        ll x = 0;
        for (int i = 0; i < it; i++) {
            sort(all(vals[i]));
            int j = lower_bound(all(vals[i]), real[i]) - vals[i].begin();
            x = x * vals[i].size() + j;
        }
        Send(x, bits[it]);
    }
}

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});
        }
    }
    vi bits = {0, 6, 10, 14, 16, 18};
    vi opt(q);
    int l = 0;
    for (int it = 1; it <= k; it++) {
        vvi vals(it, {infinity2});
        vi real(it);
        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);
            vals[opt[i]].push_back(d[it] - d[opt[i]]);
        }

        ll y = Read(l, l + bits[it], x);
        l += bits[it];

        for (int i = it - 1; i >= 0; i--) {
            sort(all(vals[i]));
            real[i] = vals[i][y % vals[i].size()];
            y /= vals[i].size();
        }

        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);
            if (real[opt[i]] > d[it] - d[opt[i]]) opt[i] = it;
        }
    }
    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 j = opt[i];
        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: 20 / 20