Submission #1224401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224401		abczz	Spy 3 (JOI24_spy3)	C++20	0 / 100	5 ms	3028 KiB

Aoi

#include "Aoi.h"
#include <iostream>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

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) {
  priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
  vector <ll> dist, P, E, virtualP;
  string S;
  ll missingedge[20000], G[300];
  vector <array<ll, 3>> adj[10000];
  dist.resize(N);
  P.resize(N);
  virtualP.resize(K);
  E.resize(N);
  for (int i=0; i<N; ++i) dist[i] = (ll)1e18, P[i] = -1;
  for (int i=0; i<M; ++i) {
    missingedge[i] = -1;
    adj[A[i]].push_back({B[i], C[i], i});
    adj[B[i]].push_back({A[i], C[i], i});
  }
  for (int i=0; i<K; ++i) G[i] = -1, virtualP[i] = -1;
  for (int i=0; i<X.size(); ++i) missingedge[X[i]] = i;
  dist[0] = 0;
  pq.push({0, 0});
  while (!pq.empty()) {
    auto [w, u] = pq.top();
    pq.pop();
    if (dist[u] != w) continue;
    for (auto [v, x, id] : adj[u]) {
      if (dist[v] > dist[u] + x) {
        dist[v] = dist[u] + x;
        P[v] = u;
        E[v] = id;
        pq.push({dist[v], v});
      }
    }
  }
  for (auto u : T) cout << dist[u] << " ";
  cout << endl;
  array<ll, 2> cnt[17];
  vector <ll> st, pv;
  for (int i=0; i<17; ++i) cnt[i] = {0, i};
  for (int i=0; i<Q; ++i) {
    ll u = T[i];
    vector <ll> V;
    while (u) {
      if (missingedge[E[u]] != -1) {
        if (G[missingedge[E[u]]] == -1) G[missingedge[E[u]]] = i;
        V.push_back(missingedge[E[u]]);
      }
      u = P[u];
    }
    if (V.empty()) st.push_back(-1), pv.push_back(-1);
    else {
      if (G[V[0]] != i) st.push_back(-1), pv.push_back(V[0]);
      if (G[V.back()] == i) st.push_back(V.back()), pv.push_back(-1);
    }
    for (int j=0; j+1<V.size(); ++j) {
      if (G[V[j]] == i && G[V[j+1]] != i) st.push_back(V[j]), pv.push_back(V[j+1]);
      if (virtualP[V[j]] == -1) virtualP[V[j]] = V[j+1];
    }
  }
  for (int i=0; i<K; ++i) ++cnt[G[i] == -1 ? 16 : G[i]][0];
  sort(cnt, cnt+17, [](auto a, auto b) {
    return a[0] < b[0];
  });
  if (cnt[0][1] > cnt[1][1]) swap(cnt[0], cnt[1]);
  for (int i=0; i<2; ++i) {
    for (int k=4; k>=0; --k) S += char('0'+min(1LL, cnt[i][1]&(1LL<<k)));
  }
  for (int i=0; i<K; ++i) {
    ll u = G[i] == -1 ? 16 : G[i];
    if (u == cnt[0][1]) S += "11110";
    else if (u == cnt[1][1]) S += "11111";
    else {
      if (u >= cnt[1][1]) --u;
      if (u >= cnt[0][1]) --u;
      for (int k=3; k>=0; --k) S += char('0'+min(1LL, u&(1LL<<k)));
    }
  }
  for (int i=0; i<Q; ++i) {
    if (st[i] == -1) S += "111111111";
    else {
      for (int k=8; k>=0; --k) S += char('0'+min(1LL, st[i]&(1LL<<k)));
    }
    if (pv[i] == -1) S += "111111111";
    else {
      for (int k=8; k>=0; --k) S += char('0'+min(1LL, pv[i]&(1LL<<k)));
    }
  }
  if (S.back() == '\n') S.pop_back();
  return S;
}

Bitaro

#include "Bitaro.h"
#include <iostream>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

vector <int> path[16];
vector <ll> dist, dist2[16], P, E, Z, H[300];
vector <array<ll, 2>> edgedir;
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
vector <array<ll, 3>> adj[10000];
void append(vector <int> &A, vector <ll> B) {
  for (auto u : B) A.push_back(u);
}
void append(vector <int> &A, vector <int> B) {
  for (auto u : B) A.push_back(u);
}
vector <ll> query(ll a, ll b, ll c) {
  for (int i=0; i<dist.size(); ++i) dist[i] = (ll)1e18, P[i] = E[i] = -1;
  dist[a] = 0;
  pq.push({0, a});
  while (!pq.empty()) {
    auto [w, u] = pq.top();
    pq.pop();
    if (dist[u] != w) continue;
    for (auto [v, x, id] : adj[u]) {
      if (x == (ll)1e18 || dist[v] <= dist[u]+x) continue;
      dist[v] = dist[u] + x;
      P[v] = u, E[v] = id;
      pq.push({dist[v], v});
    }
  }
  if (dist[b] > dist[c]) b = c;
  vector <ll> edge;
  while (b != a) {
    edge.push_back(E[b]);
    b = P[b];
  }
  reverse(edge.begin(), edge.end());
  return edge;
}

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 <ll> G, en;
  edgedir.resize(M);
  Z.resize(M);
  dist.resize(N);
  for (int i=0; i<Q; ++i) dist2[i].resize(N);
  P.resize(N);
  E.resize(N);
  G.resize(K);
  en.resize(K);
  for (auto u : X) C[u] = (ll)1e18;
  for (int i=0; i<M; ++i) {
    edgedir[i] = {-1, -1};
    Z[i] = -1;
    adj[A[i]].push_back({B[i], C[i], i});
    adj[B[i]].push_back({A[i], C[i], i});
  }
  for (int i=0; i<X.size(); ++i) Z[X[i]] = i;
  int pt = 0;
  vector <ll> U;
  for (int i=0; i<2; ++i) {
    ll cur = 0;
    for (int k=4; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
    U.push_back(cur);
  }
  for (int i=0; i<K; ++i) {
    en[i] = -1;
    ll cur = 0;
    for (int k=3; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
    if (cur == 15) {
      if (S[pt++] == '0') G[i] = (U[0] == 16 ? -1 : U[0]);
      else G[i] = (U[1] == 16 ? -1 : U[1]);
    }
    else {
      if (cur >= U[0]) ++cur;
      if (cur >= U[1]) ++cur;
      G[i] = (cur == 16 ? -1 : cur);
    }
  }
  vector <ll> st, pv, rt;
  for (int i=0; i<Q; ++i) {
    ll cur = 0;
    for (int k=8; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
    st.push_back(cur == (1LL<<9)-1 ? -1 : cur);
    cur = 0;
    for (int k=8; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
    pv.push_back(cur == (1LL<<9)-1 ? -1 : cur);
    rt.push_back(-1);
    if (pv[i] != -1) H[pv[i]].push_back(i);
    if (pv[i] == -1 && st[i] == -1) append(path[i], vector<ll>{query(0, T[i], T[i])});
    else if (pv[i] == -1) {
      append(path[i], vector<ll>{query(0, A[X[st[i]]], B[X[st[i]]])});
      path[i].push_back(X[st[i]]);
      if (dist[A[X[st[i]]]] > dist[B[X[st[i]]]]) rt[i] = A[X[st[i]]];
      else rt[i] = B[X[st[i]]];
    }
  }
  for (int i=0; i<Q; ++i) {
    for (int j=0; j<N; ++j) dist[j] = (ll)1e18, P[j] = -1, E[j] = -1;
    if (pv[i] == -1 && st[i] == -1) {
      answer(path[i]);
      continue;
    }
    dist[rt[i]] = 0;
    pq.push({0, rt[i]});
    while (!pq.empty()) {
      auto [w, u] = pq.top();
      pq.pop();
      if (dist[u] != w) continue;
      for (auto [v, x, id] : adj[u]) {
        if (x == (ll)1e18) {
          if (Z[id] != -1 && G[Z[id]] == i && dist[v] > dist[u]+1) {
            dist[v] = dist[u]+1;
            P[v] = u, E[v] = id;
            pq.push({dist[v], v});
          }
        }
        else if (dist[v] > dist[u]+x) {
          dist[v] = dist[u]+x;
          P[v] = u, E[v] = id;
          pq.push({dist[v], v});
        }
      }
    }
    vector <ll> tmp;
    ll u = T[i];
    while (u != rt[i]) {
      tmp.push_back(E[u]);
      u = P[u];
    }
    reverse(tmp.begin(), tmp.end());
    append(path[i], tmp);
    answer(path[i]);
    u = T[i];
    while (!path[i].empty()) {
      if (Z[path[i].back()] != -1) {
        if (G[Z[path[i].back()]] != i) break;
        for (auto z : H[Z[path[i].back()]]) {
          append(path[z], path[i]);
          rt[z] = u;
        }
      }
      if (u == rt[i]) break;
      u = (u == A[path[i].back()] ? B[path[i].back()] : A[path[i].back()]);
      path[i].pop_back();
    }
  }
}

• Subtask 1: 0 / 100