Submission #1234521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234521		chaeryeong	Spy 3 (JOI24_spy3)	C++20	0 / 100	1103 ms	979448 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) {
    vector <bool> bad(M, 0);
    for (auto i : X) {
        bad[i] = 1;
    }
    vector <ll> dist(N, (ll)1e18);
    vector <array <ll, 2>> adj[N];
    dist[0] = 0;
    for (int i = 0; i < M; i++) {
        if (bad[i]) {
            continue;
        }
        adj[A[i]].push_back({B[i], C[i]});
        adj[B[i]].push_back({A[i], C[i]});
    }
    for (int i = 1; i < N; i++) {
        adj[0].push_back({i, (ll)1e18});
        adj[i].push_back({0, (ll)1e18});
    }
    priority_queue <array <ll, 2>, vector <array <ll, 2>>, 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 ((j != 0 && par[j] == -1) || dist[j] > w + d) {
                dist[j] = w + d;
                par[j] = node;
                pq.push({dist[j], j});
            }
        }
    }
    sort(X.begin(), X.end());
    vector <int> updates;
    for (auto i : X) {
        adj[A[i]].push_back({B[i], C[i]});
        adj[B[i]].push_back({A[i], C[i]});
        if (dist[A[i]] > dist[B[i]] + C[i]) {
            pair <ll, ll> mn = {dist[A[i]], A[i]};
            dist[A[i]] = dist[B[i]] + C[i];
            priority_queue <array <ll, 2>, vector <array <ll, 2>>, greater <>> pq;
            pq.push({dist[A[i]], A[i]});
            while (!pq.empty()) {
                auto [d, node] = pq.top();
                pq.pop();
                if (d > dist[node]) {
                    continue;
                }
                for (auto [j, w] : adj[node]) {
                    if ((j != 0 && par[j] == -1) || dist[j] > w + d) {
                        par[j] = node;
                        mn = min(mn, pair <ll, ll> {dist[j], j});
                        dist[j] = w + d;
                        pq.push({dist[j], j});
                    }
                }
            }
            updates.push_back(mn.second);
        } else if (dist[B[i]] > dist[A[i]] + C[i]) {
            pair <ll, ll> mn = {dist[B[i]], B[i]};
            dist[B[i]] = dist[A[i]] + C[i];
            priority_queue <array <ll, 2>, vector <array <ll, 2>>, greater <>> pq;
            pq.push({dist[B[i]], B[i]});
            while (!pq.empty()) {
                auto [d, node] = pq.top();
                pq.pop();
                if (d > dist[node]) {
                    continue;
                }
                for (auto [j, w] : adj[node]) {
                    if ((j != 0 && par[j] == -1) || dist[j] > w + d) {
                        mn = min(mn, pair <ll, ll> {dist[j], j});
                        dist[j] = w + d;
                        pq.push({dist[j], j});
                    }
                }
            }
          //  cout << A[i] << " " << B[i] << ": " << mn.second << '\n';
            updates.push_back(mn.second);
        } else {
            updates.push_back(-1);
        }
    }
/*    for (auto i : dist) {
        cout << i << " ";
    }
    cout << '\n';*/
    string s;
    for (auto i : updates) {
        if (i == -1) {
            s += (char)('0');
        } else {
            s += (char)('1');
            for (int j = __lg(N - 1); j >= 0; j--) {
                s += (char)(((i >> j) & 1) + '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) {
  vector <bool> bad(M, 0);
  for (auto i : X) {
      bad[i] = 1;
  }
  vector <ll> dist(N, (ll)1e18);
  vector <array <ll, 2>> adj[N];
  dist[0] = 0;
  vector <int> par(N, -1);
  for (int i = 0; i < M; i++) {
      if (bad[i]) {
          continue;
      }
      adj[A[i]].push_back({B[i], C[i]});
      adj[B[i]].push_back({A[i], C[i]});
  }
  for (int i = 1; i < N; i++) {
      adj[0].push_back({i, (ll)1e18});
      adj[i].push_back({0, (ll)1e18});
  }
  priority_queue <array <ll, 2>, vector <array <ll, 2>>, greater <>> pq;
  pq.push({0, 0});
  while (!pq.empty()) {
      auto [d, node] = pq.top();
      pq.pop();
      if (d > dist[node]) {
          continue;
      }
      for (auto [j, w] : adj[node]) {
          if ((j != 0 && par[j] == -1) || dist[j] > w + d) {
              assert(j != 0);
              par[j] = node;
              dist[j] = w + d;
              pq.push({dist[j], j});
          }
      }
  }
  sort(X.begin(), X.end());
  int b = 0;
  for (auto i : X) {
    if (s[b++] == '0') {
      continue;
    }
    int u = 0;
    for (int j = __lg(N - 1); j >= 0; j--) {
      u = 2 * u;
      if (s[b++] == '1') {
        u++;
      }
    }
   // cout << i << " " << u << ' ';
    bool flag = 0;
    int t = A[i];
    while (t != -1) {
      flag |= t == u;
      t = par[t];
    }
    if (flag) {
      int t = A[i];
      vector <int> zz;
      while (t != u) {
        zz.push_back(t);
        t = par[t];
      }
      zz.push_back(u);
      for (int i = (int)zz.size() - 1; i > 0; i--) {
        par[zz[i]] = zz[i - 1];
      }
      par[A[i]] = B[i];
    } else {
      int t = B[i];
      vector <int> zz;
      while (t != u) {
        zz.push_back(t);
        t = par[t];
      }
      zz.push_back(u);
      for (int i = (int)zz.size() - 1; i > 0; i--) {
        par[zz[i]] = zz[i - 1];
      }
      par[B[i]] = A[i];
    }
  //  cout << u << " " << par[u] << '\n';
  }
/*  for (int i = 0; i < N; i++) {
    cout << par[i] << " ";
  }
  cout << '\n';*/
  map <pair <int, int>, int> mp;
  for (int i = 0; i < M; i++) {
    mp[{A[i], B[i]}] = i;
    mp[{B[i], A[i]}] = i;
  }
  for (auto i : T) {
    vector <int> ret;
    int u = i;
    while (u != 0) {
      ret.push_back(u);
      u = par[u];
    }
    ret.push_back(0);
    reverse(ret.begin(), ret.end());
    vector <int> roads;
    for (int i = 0; i + 1 < (int)ret.size(); i++) {
      roads.push_back(mp[{ret[i], ret[i + 1]}]);
    }
    answer(roads);
  }
}

• Subtask 1: 0 / 100