Submission #1235206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235206		chaeryeong	Spy 3 (JOI24_spy3)	C++20	23 / 100	554 ms	5744 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());
    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];
        //cout << u << '\n';
        vector <int> path;
        while (u != -1) {
            path.push_back(u);
            u = par[u];
        }
/*        for (auto i : path) {
            cout << i << " ";
        }
        cout << '\n';*/
        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');
            }
        }
    }
   // cout << s << '\n';
    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());
  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];
   // cout << u << '\n';
/*    for (auto j : used) {
      cout << j << " ";
    }
    cout << '\n';*/
    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);
/*        cout << u << " " << pos << " " << d << '\n';
      for (int i = 0; i < N; i++) {
        cout << par[i] << " ";
      }
      cout << '\n';*/
      int t = pos;
      vector <int> g;
      while (u != t) {
        g.push_back(mp[{t, par[t]}]);
        t = par[t];
        if (t == -1) {
          break;
        }
      }
      reverse(g.begin(), g.end());
      for (auto j : g) {
        path.push_back(j);
      }
      if (u == -1) {
        exit(0);
      }
      if (d == -1 || d >= K) {
        break;
      }
      u = pos;
      path.push_back(X[d]);
      if (u == A[X[d]]) {
        u = B[X[d]];
      } else {
        u = A[X[d]];
      }
      used[d] = 0;
    }
    reverse(path.begin(), path.end());
/*    for (auto i : path) {
      cout << A[i] << " " << B[i] << '\n';
    }*/
    answer(path);
  }
}

• Subtask 1: 23 / 100