Submission #978206

#	Time	Username	Problem	Language	Result	Execution time	Memory
978206		model_code	Spy 3 (JOI24_spy3)	C++17	100 / 100	81 ms	7144 KiB

Aoi

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

using namespace std;

using ll = long long;

namespace {
    const ll linf = 1LL << 60;

    string encode(ll num, int len) {
        string s;
        for (int i = len - 1; i >= 0; i--) s.push_back('0' + (num >> i & 1));
        return s;
    }

    // {dist, pre}
    pair<vector<ll>, vector<int>> dijkstra(int n, const vector<int> &a, const vector<int> &b, const vector<ll> &c) {
        vector<vector<tuple<int, ll, int>>> G(n);
        for (int i = 0; i < a.size(); i++) {
            if (c[i] == -1) continue;
            G[a[i]].emplace_back(b[i], c[i], i);
            G[b[i]].emplace_back(a[i], c[i], i);
        }
        vector<ll> dist(n, linf);
        vector<int> pre(n, -1);
        priority_queue<pair<ll, int>, vector<pair<ll, int >>, greater<>> pq;
        dist[0] = 0;
        pq.emplace(0, 0);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, len, id]: G[u]) {
                if (dist[v] > d + len) {
                    dist[v] = d + len;
                    pre[v] = id;
                    pq.emplace(dist[v], v);
                }
            }
        }
        return {dist, pre};
    }
}

std::string aoi(int n, int m, int q, int k, std::vector<int> a,
                std::vector<int> b, std::vector<long long> c,
                std::vector<int> t, std::vector<int> x) {
    vector<int> x_id(m, -1);
    for (int i = 0; i < k; i++) x_id[x[i]] = i;
    auto [dist, pre] = dijkstra(n, a, b, c);
    vector<vector<int>> G(n + q);   // 最短路木
    for (int i = 1; i < n; i++) {
        G[a[pre[i]] ^ b[pre[i]] ^ i].push_back(i);
    }
    vector<int> bit(n);  // bit[i] : é ‚ç‚¹ i の subtree に含まれる t[j] たちの集合を 0 ~ (1<<q)-1 で
    for (int i = 0; i < q; i++) bit[t[i]] = 1 << i;
    auto dfs = [&](auto &dfs, int u) -> void {
        for (int v: G[u]) {
            dfs(dfs, v);
            bit[u] |= bit[v];
        }
    };
    dfs(dfs, 0);
    vector<int> s(k);
    for (int i = 0; i < k; i++) {
        int e = x[i];
        if (dist[a[e]] > dist[b[e]]) swap(a[e], b[e]);
        if (pre[b[e]] == e) {
            s[i] = bit[b[e]];
        }
    }
    sort(bit.begin(), bit.end());
    bit.erase(unique(bit.begin(), bit.end()), bit.end());
    // è¦ç´ æ•°ã®æ˜‡é †ã«ã‚½ãƒ¼ãƒˆ
    sort(bit.begin(), bit.end(), [](int a, int b) { return __builtin_popcount(a) < __builtin_popcount(b); });
    vector<pair<int, int>> div(1 << q);   // div[i] : 集合 i は何と何に分割されるか
    {
        set<int> st;
        for (int i = 0; i < q; i++) {
            st.insert(1 << i);
        }
        for (int i: bit) {
            if (!i) continue;
            vector<int> mg;
            for (int j: st) if ((j & i) == j) mg.push_back(j);
            for (int j = 1; j < mg.size(); j++) {
                int now = mg[j - 1] | mg[j];
                div[now] = {mg[j - 1], mg[j]};
                st.erase(mg[j - 1]);
                st.erase(mg[j]);
                st.insert(now);
                mg[j] = now;
            }
        }
    }
    vector binom(q, vector<ll>(q));
    for (int i = 0; i < q; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }
    vector<ll> dp(q + 1);   // dp[i] : {1, 2, ..., i} をいくつかの集合に分割する方法の数
    dp[1] = 1;
    for (int i = 2; i <= q; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] += binom[i - 1][j - 1] * dp[j] * dp[i - j];
        }
    }
    vector<int> ls = {0};
    auto f = [&](auto &f, int now) -> ll {
        ls.push_back(now);
        int cnt = __builtin_popcount(now);
        if (cnt == 1) return 0;
        vector<int> fac;
        for (int i = 0; i < q; i++) if (now >> i & 1) fac.push_back(i);
        auto [l, r] = div[now];
        if (~l >> fac[0] & 1) swap(l, r);
        int lc = __builtin_popcount(l);
        int rc = __builtin_popcount(r);
        ll res = 0;
        for (int i = 1; i < lc; i++) {
            res += binom[cnt - 1][i - 1] * dp[i] * dp[cnt - i];
        }
        vector<int> nv;
        for (int i = 0; i < cnt; i++) {
            if (l >> fac[i] & 1) nv.push_back(0);
            else nv.push_back(1);
        }
        vector<int> v;
        for (int i = 0; i < lc; i++) v.push_back(0);
        for (int i = 0; i < rc; i++) v.push_back(1);
        do {
            if (v == nv) break;
            res += dp[lc] * dp[rc];
        } while (next_permutation(v.begin(), v.end()));
        ll lid = f(f, l);
        ll rid = f(f, r);
        res += lid * dp[rc] + rid;
        return res;
    };
    string res = encode(f(f, (1 << q) - 1), 53);
    for (int i = 0; i < k; i++) {
        res += encode(find(ls.begin(), ls.end(), s[i]) - ls.begin(), 5);
    }
    return res;
}

Bitaro

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

using namespace std;

namespace {
    using ll = long long;

    const ll linf = 1LL << 60;

    ll decode(string::iterator l, string::iterator r) {
        ll res = 0;
        while (l < r) {
            res *= 2;
            res += *l - '0';
            ++l;
        }
        return res;
    }

    // {dist, pre}
    pair<vector<ll>, vector<int>> dijkstra(int n, const vector<int> &a, const vector<int> &b, const vector<ll> &c) {
        vector<vector<tuple<int, ll, int>>> G(n);
        for (int i = 0; i < a.size(); i++) {
            if (c[i] == -1) continue;
            G[a[i]].emplace_back(b[i], c[i], i);
            G[b[i]].emplace_back(a[i], c[i], i);
        }
        vector<ll> dist(n, linf);
        vector<int> pre(n, -1);
        priority_queue<pair<ll, int>, vector<pair<ll, int >>, greater<>> pq;
        dist[0] = 0;
        pq.emplace(0, 0);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, len, id]: G[u]) {
                if (dist[v] > d + len) {
                    dist[v] = d + len;
                    pre[v] = id;
                    pq.emplace(dist[v], v);
                }
            }
        }
        return {dist, pre};
    }
}

void bitaro(int n, int m, int q, int k, std::vector<int> a, std::vector<int> b,
            std::vector<long long> c, std::vector<int> t, std::vector<int> x,
            std::string s) {
    vector binom(q, vector<ll>(q));
    for (int i = 0; i < q; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }
    vector<ll> dp(q + 1);   // dp[i] : {1, 2, ..., i} をいくつかの集合に分割する方法の数
    dp[1] = 1;
    for (int i = 2; i <= q; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] += binom[i - 1][j - 1] * dp[j] * dp[i - j];
        }
    }
    vector<int> ls = {0};
    auto f = [&](auto &f, int now, ll val) -> void {
        ls.push_back(now);
        int cnt = __builtin_popcount(now);
        if (cnt == 1) return;
        vector<int> fac;
        for (int i = 0; i < q; i++) if (now >> i & 1) fac.push_back(i);
        int lc = 1;
        for (;; lc++) {
            ll cur = binom[cnt - 1][lc - 1] * dp[lc] * dp[cnt - lc];
            if (val < cur) break;
            val -= cur;
        }
        int rc = cnt - lc;
        vector<int> v;
        for (int i = 0; i < lc; i++) v.push_back(0);
        for (int i = 0; i < rc; i++) v.push_back(1);
        do {
            if (val < dp[lc] * dp[rc]) break;
            val -= dp[lc] * dp[rc];
        } while (next_permutation(v.begin(), v.end()));
        int l = 0, r = 0;
        for (int i = 0; i < cnt; i++) {
            if (!v[i]) l |= 1 << fac[i];
            else r |= 1 << fac[i];
        }
        f(f, l, val / dp[rc]);
        f(f, r, val % dp[rc]);
    };
    f(f, (1 << q) - 1, decode(s.begin(), s.begin() + 53));
    vector use(q, vector<bool>(k));
    int iter = 53;
    for (int i = 0; i < k; i++) {
        int bit = ls[decode(s.begin() + iter, s.begin() + iter + 5)];
        iter += 5;
        for (int j = 0; j < q; j++) if (bit >> j & 1) use[j][i] = true;
    }
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < k; j++) {
            if (use[i][j]) c[x[j]] = 0;
        }
        auto [dist, pre] = dijkstra(n, a, b, c);
        int now = t[i];
        vector<int> es;
        while (now) {
            es.push_back(pre[now]);
            now = a[pre[now]] ^ b[pre[now]] ^ now;
        }
        reverse(es.begin(), es.end());
        answer(es);
        for (int j = 0; j < k; j++) c[x[j]] = -1;
    }
}

Compilation message (stderr)

Aoi.cpp: In function 'std::pair<std::vector<long long int>, std::vector<int> > {anonymous}::dijkstra(int, const std::vector<int>&, const std::vector<int>&, const std::vector<long long int>&)':
Aoi.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
Aoi.cpp: In function 'std::string aoi(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>)':
Aoi.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for (int j = 1; j < mg.size(); j++) {
      |                             ~~^~~~~~~~~~~

Bitaro.cpp: In function 'std::pair<std::vector<long long int>, std::vector<int> > {anonymous}::dijkstra(int, const std::vector<int>&, const std::vector<int>&, const std::vector<long long int>&)':
Bitaro.cpp:24:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 100 / 100