Submission #1011208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011208		huutuan	Spy 3 (JOI24_spy3)	C++17	23 / 100	60 ms	6776 KiB

Aoi

#include "Aoi.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace Aoi{
   const int N=1e4+10, M=2e4+10;
   int n, m;
   pair<pair<int, int>, int> edge[M];
   vector<int> g[N];
   int tr[N], f[N];
   void dijkstra(){
      memset(f, 0x3f, sizeof f);
      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
      pq.emplace(f[0]=0, 0);
      while (pq.size()){
         int u=pq.top().second, d=pq.top().first;
         pq.pop();
         if (f[u]!=d) continue;
         for (int i:g[u]){
            int v=edge[i].first.first^edge[i].first.second^u;
            int w=edge[i].second;
            if (f[v]>d+w) pq.emplace(f[v]=d+w, v), tr[v]=i;
         }
      }
   }
   bool used[M];
   void trace(int u, vector<int> &ans){
      if (u==0) return;
      ans.push_back(tr[u]);
      return trace(edge[tr[u]].first.first^edge[tr[u]].first.second^u, ans);
   }
   string solve(int32_t _N, int32_t _M, int32_t Q, int32_t K, vector<int32_t> A,
                vector<int32_t> B, vector<long long> C,
                vector<int32_t> T, vector<int32_t> X){
      n=_N, m=_M;
      for (int i=0; i<m; ++i){
         edge[i]={{A[i], B[i]}, C[i]};
         g[A[i]].push_back(i);
         g[B[i]].push_back(i);
      }
      dijkstra();
      string ans;
      for (int i:T){
         string cur(K, '0');
         vector<int> path;
         trace(i, path);
         for (int j:path) used[j]=1;
         for (int j=0; j<K; ++j) cur[j]=used[X[j]]+'0';
         for (int j:path) used[j]=0;
         ans+=cur;
      }
      #ifdef sus
      ofstream out("spy3.out");
      for (int i=0; i<n; ++i) out << f[i] << ' ';
      #endif
      return ans;
   }
}

string aoi(int32_t N, int32_t M, int32_t Q, int32_t K, vector<int32_t> A,
           vector<int32_t> B, vector<long long> C,
           vector<int32_t> T, vector<int32_t> X) {
   return Aoi::solve(N, M, Q, K, A, B, C, T, X);
}

Bitaro

#include "Bitaro.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace Bitaro{
   const int N=1e4+10, M=2e4+10, inf=1e18;
   int n, m, q, k;
   pair<pair<int, int>, int> edge[M];
   vector<int> g[N];
   int tr[N];
   pair<int, int> f[N];
   bool used[M];
   void trace(int u, vector<int32_t> &ans){
      if (u==0) return;
      ans.push_back(tr[u]);
      return trace(edge[tr[u]].first.first^edge[tr[u]].first.second^u, ans);
   }
   vector<int32_t> dijkstra(int t, vector<int> id){
      for (int i=0; i<n; ++i) f[i]={inf, inf};
      f[0]={0, 0};
      priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> pq;
      pq.emplace(f[0], 0);
      set<int> st(id.begin(), id.end());
      int cur=0;
      while (pq.size()){
         auto d=pq.top().first; int u=pq.top().second;
         pq.pop();
         if (f[u]!=d || d.first!=cur) continue;
         if (u==t){
            vector<int32_t> ans;
            trace(t, ans);
            reverse(ans.begin(), ans.end());
            return ans;
         }
         bool check=0;
         for (int i:g[u]){
            if (check) continue;
            if (st.count(i)){
               ++cur;
               int v=edge[i].first.first^edge[i].first.second^u, w=edge[i].second;
               pq.emplace(f[v]={cur, d.second}, v);
               tr[v]=i;
               check=1;
               st.erase(i);
            }
         }
         for (int i:g[u]){
            if (check || used[i]) continue;
            int v=edge[i].first.first^edge[i].first.second^u, w=edge[i].second;
            if (f[v].second>d.second+w) pq.emplace(f[v]={d.first, d.second+w}, v), tr[v]=i;
         }
      }
      assert(false);
      return {};
   }
   void solve(int32_t _N, int32_t _M, int32_t Q, int32_t K, vector<int32_t> A, vector<int32_t> B,
              vector<long long> C, vector<int32_t> T, vector<int32_t> X,
              string s){
      n=_N, m=_M, q=Q, k=K;
      for (int i:X) used[i]=1;
      for (int i=0; i<m; ++i){
         edge[i]={{A[i], B[i]}, C[i]};
         g[A[i]].push_back(i);
         g[B[i]].push_back(i);
      }
      for (int i=0; i<Q; ++i){
         string t=s.substr(i*K, K);
         vector<int> id;
         for (int j=0; j<K; ++j) if (t[j]=='1') id.push_back(X[j]);
         auto ans=dijkstra(T[i], id);
         answer(ans);
      }
   }
}

void bitaro(int32_t N, int32_t M, int32_t Q, int32_t K, vector<int32_t> A, vector<int32_t> B,
            vector<long long> C, vector<int32_t> T, vector<int32_t> X,
            string s) {
   Bitaro::solve(N, M, Q, K, A, B, C, T, X, s);
}

Compilation message (stderr)

Bitaro.cpp: In function 'std::vector<int> Bitaro::dijkstra(long long int, std::vector<long long int>)':
Bitaro.cpp:44:66: warning: unused variable 'w' [-Wunused-variable]
   44 |                int v=edge[i].first.first^edge[i].first.second^u, w=edge[i].second;
      |                                                                  ^

• Subtask 1: 23 / 100