Submission #1239791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239791		The_Samurai	Spy 3 (JOI24_spy3)	C++20	0 / 100	10 ms	2004 KiB

Aoi

#include "Aoi.h"
#include "bits/stdc++.h"

namespace {
    using namespace std;
    using ll = long long;
    const ll inf = 1e18;
    int variable_example = 0;

    int function_example(int a, int b) { return a + b; }

}  // namespace

std::string aoi(int n, int m, int q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> w, std::vector<int> T, std::vector<int> X) {
    sort(X.begin(), X.end());
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        g[A[i]].emplace_back(B[i], i);
        g[B[i]].emplace_back(A[i], i);
    }

    auto get = [&](int to) -> vector<int> {
        vector<ll> dist(n, inf);
        vector<pair<int, int>> par(n);
        priority_queue<pair<ll, int>> pq;
        dist[0] = 0; pq.emplace(0, 0);
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (dist[u] < -d) continue;
            for (auto [v, i]: g[u]) {
                if (dist[v] <= dist[u] + w[i]) continue;
                dist[v] = dist[u] + w[i];
                par[v] = make_pair(u, i);
                pq.emplace(-dist[v], v);
            }
        }
        int now = to;
        vector<int> ans;
        while (now != 0) {
            ans.emplace_back(par[now].second);
            now = par[now].first;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    };


    vector<int> id(m, -1);
    for (int i = 0; i < K; i++) id[X[i]] = i;
    string ans(40 * K, '0');
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < 40; j++) {
            // cout << w[X[i]] << ' ' << j << ' ' << (w[X[i]] >> j & 1ll) << endl;
            ans[i * 40 + j] = (w[X[i]] >> j & 1ll) + '0';
        }
    }
    // for (int i = 0; i < q; i++) {
    //     auto way = get(T[i]);
    //     for (int pos: way) {
    //         if (id[pos] != -1) ans[i * K + id[pos]] = '1';
    //     }
    // }
    return ans;
}

Bitaro

#include "Bitaro.h"
#include "bits/stdc++.h"

namespace {
    using namespace std;
    using ll = long long;
    const ll inf = 1e18;
    int variable_example = 0;

    int function_example(int a, int b) { return a + b; }

}  // namespace

void bitaro(int n, int m, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> w, std::vector<int> T, std::vector<int> X, std::string s) {
    sort(X.begin(), X.end());
    // cout << '\t' << s << endl;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        g[A[i]].emplace_back(B[i], i);
        g[B[i]].emplace_back(A[i], i);
    }
    for (int i = 0; i < K; i++) {
        w[X[i]] = 0;
        for (int j = 0; j < 40; j++) w[X[i]] += (ll((s[i * 40 + j] - '0'))) << j;
    }
    // vector<bool> can(m);
    // vector<int> id(m, -1);
    // for (int i = 0; i < K; i++) id[X[i]] = i;

    auto get = [&](int to) -> vector<int> {
        vector<ll> dist(n, inf);
        vector<pair<int, int>> par(n);
        priority_queue<pair<ll, int>> pq;
        dist[0] = 0; pq.emplace(0, 0);
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (dist[u] < -d) continue;
            for (auto [v, i]: g[u]) {
                ll now = dist[u];
                // if (id[i] == -1) now += w[i];
                // else now += can[i] ? 0 : inf;
                now += w[i];
                if (dist[v] <= dist[u] + now) continue;
                dist[v] = dist[u] + now;
                par[v] = make_pair(u, i);
                pq.emplace(-dist[v], v);
            }
        }
        int now = to;
        vector<int> ans;
        while (now != 0) {
            ans.emplace_back(par[now].second);
            now = par[now].first;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    };

    for (int i = 0; i < Q; i++) {
        // for (int j = 0; j < K; j++) can[X[j]] = s[i * K + j] - '0';
        auto way = get(T[i]);
        // for (int j = 0; j < K; j++) can[X[j]] = false;
        answer(way);
    }
}

• Subtask 1: 0 / 100