Submission #1184332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184332		rxlfd314	Spy 3 (JOI24_spy3)	C++20	0 / 100	1079 ms	527684 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) {
  vt<int> xind(M, -1);
  FOR(i, 0, K-1)
    xind[X[i]] = i;
  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<pair<ll, int>, vt<pair<ll, int>>, greater<pair<ll, int>>> 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;
      }
  }
  
  string ret;
  FOR(q, 0, Q-1) {
    int cur = T[q];
    vt<int> need(K);
    while (cur != 0) {
      if (xind[back[cur]] >= 0)
        need[xind[back[cur]]] = 1;
      cur = A[back[cur]] ^ B[back[cur]] ^ cur;
    }
    for (const auto &i : need)
      ret.push_back('0' + i);
  }
  
  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(x, 0, Q-1) {
    FOR(i, 0, K-1)
      C[X[i]] = s[x*K+i] - '0' ? 1 : (ll)1e18;
    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});
    }
    
    priority_queue<pair<ll, int>, vt<pair<ll, int>>, greater<pair<ll, int>>> pq;
    vt<ll> dist(N, LLONG_MAX);
    vt<int> back(N);
    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;
        }
    }
    
    vt<int> ans;
    for (int cur = T[x]; cur; cur = A[back[cur]] ^ B[back[cur]] ^ cur)
      ans.push_back(back[cur]);
    reverse(all(ans));
    answer(ans);
  }
}

• Subtask 1: 0 / 100