Submission #1235188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235188		chaeryeong	Spy 3 (JOI24_spy3)	C++20	0 / 100	33 ms	4972 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<ll> C,
                std::vector<int> T, std::vector<int> X) {
    //Lmao how did I not notice the Q
  sort(X.begin(), X.end());
  sort(T.begin(), T.end());
    vector <pair <ll, ll>> adj[N];
    vector <int> bad(M, 0);
    for (auto i : X) {
        bad[i] = 1;
    }
    map <pair <int, int>, int> mp;
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back({B[i], C[i]});
        adj[B[i]].push_back({A[i], C[i]});
        mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
    }
    vector <ll> dist(N, (ll)1e18);
    dist[0] = 0;
    priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq;
    pq.push({0, 0});
    vector <int> par(N, -1);
    while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();
        if (d > dist[node]) {
            continue;
        }
        for (auto [j, w] : adj[node]) {
            if (dist[j] > w + d) {
                dist[j] = w + d;
                pq.push({dist[j], j});
                par[j] = node;
            }
        }
    }
    string s;
    for (int i = 0; i < Q; i++) {
        int u = T[i];
        vector <int> path;
        while (u != -1) {
            path.push_back(u);
            u = par[u];
        }
        vector <int> useful(M, 0);
        for (int j = 0; j + 1 < (int)path.size(); j++) {
            if (bad[mp[{path[j], path[j + 1]}]]) {
                useful[mp[{path[j], path[j + 1]}]] = 1;
            }
        }   
        for (int j = 0; j < M; j++) {
            if (bad[j]) {
                s += (char)(useful[j] + '0');
            }
        }
    }
    return s;
}

Bitaro

#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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) {
  sort(X.begin(), X.end());
  sort(T.begin(), T.end());
  map <pair <int, int>, int> mp;
  vector <int> bad(M, 0);
  for (auto i : X) {
    bad[i] = 1;
  }
  vector <pair <ll, ll>> adj[N];
  for (int i = 0; i < M; i++) {
    mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
    if (!bad[i]) {
      adj[A[i]].push_back({B[i], C[i]});
      adj[B[i]].push_back({A[i], C[i]});
    }
  }
  assert(s.length() == Q * K);
  for (int i = 0; i < Q; i++) {
    vector <int> used(K, 0);
    for (int j = i * K; j < (i + 1) * K; j++) {
      used[j - i * K] = s[j] - '0';
    }
    int u = T[i];
    vector <int> path;
    while (true) {
      vector <ll> dist(N, (ll)1e18);
      assert(u != -1);
      dist[u] = 0;
      priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq;
      pq.push({dist[u], u});
      vector <int> par(N, -1);
      while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();
        if (d > dist[node]) {
          continue;
        }
        for (auto [j, w] : adj[node]) {
          if (dist[j] > d + w) {
            dist[j] = d + w;
            par[j] = node;
            pq.push({dist[j], j});
          }
        }
      }
      int pos = 0, d = -1;
      for (int i = 0; i < K; i++) {
        if (!used[i]) {
          continue;
        }
        if (used[i] && dist[A[X[i]]] < dist[pos]) {
          pos = A[X[i]]; d = i;
        }
        if (used[i] && dist[B[X[i]]] < dist[pos]) {
          pos = B[X[i]]; d = i;
        }
      }
      assert(u != -1);
      while (u != pos) {
        path.push_back(mp[{u, par[u]}]);
        u = par[u];
        assert(u != -1);
      }
      if (d == -1 || d >= K) {
        break;
      }
      path.push_back(X[d]);
      if (u == A[X[d]]) {
        u = B[X[d]];
      } else {
        u = A[X[d]];
      }
    }
    reverse(path.begin(), path.end());
    answer(path);
  }
}

• Subtask 1: 0 / 100