Submission #1012787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012787		huutuan	Spy 3 (JOI24_spy3)	C++17	23 / 100	58 ms	6560 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;
      }
      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], f[N];
   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);
   }
   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;
         }
      }
   }
   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=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') edge[X[j]].second=0; else edge[X[j]].second=inf;
         dijkstra();
         vector<int32_t> ans;
         trace(T[i], ans);
         reverse(ans.begin(), ans.end());
         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);
}

• Subtask 1: 23 / 100