Submission #1184282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184282		rxlfd314	Spy 3 (JOI24_spy3)	C++20	8 / 100	15 ms	2740 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

namespace {
}

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) {
  string ret;
  for (const auto &i : X)
    FOR(j, 0, 39)
      ret.push_back('0' + ((C[i] & 1ll << j) > 0));
  return ret;
}

Bitaro

#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
namespace {
}  // namespace

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) {
  FOR(i, 0, K-1) {
    C[X[i]] = 0;
    FOR(j, 0, 39)
      C[X[i]] |= ll(s[40*i+j] - '0') << j;
  }
  vt<vt<ari2>> adj(N);
  FOR(i, 0, M-1) {
    adj[A[i]].push_back({B[i], i});
    adj[B[i]].push_back({A[i], i});
  }
  vt<ll> dist(N, LLONG_MAX);
  vt<int> back(N);
  priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
  pq.push({dist[0] = 0, 0});
  while (size(pq)) {
    const auto [d, i] = pq.top();
    pq.pop();
    if (d > dist[i]) continue;
    for (const auto &[j, e] : adj[i])
      if (d + C[e] < dist[j]) {
        pq.push({dist[j] = d + C[e], j});
        back[j] = e;
      }
  }
  for (const auto &x : T) {
    vt<int> ans;
    for (int cur = x; cur; cur = A[back[cur]] ^ B[back[cur]] ^ cur)
      ans.push_back(back[cur]);
    reverse(all(ans));
    #ifdef DEBUG
    cout << x << '\n';
    for (const auto &i : ans)
      cout << i << ' ';
    cout << '\n';
    #endif
    answer(ans);
  }
}

• Subtask 1: 8 / 100