Submission #1012842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012842		huutuan	Spy 3 (JOI24_spy3)	C++17	100 / 100	53 ms	7040 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];
   int t[M], p[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 del[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);
      }
      for (int i:X) del[i]=1, t[i]=Q;
      dijkstra();
      string ans;
      for (int i=0; i<Q; ++i){
         p[i]=K;
         vector<int> path;
         trace(T[i], path);
         for (int j:path){
            if (del[j]){
               if (t[j]<i && p[i]==K){
                  p[i]=find(X.begin(), X.end(), j)-X.begin();
               }
               t[j]=min(t[j], i);
            }
         }
      }
      for (int i=0; i<K; i+=11){
         int val=0;
         for (int j=i, pw=1; j<K && j<i+11; ++j, pw*=17){
            val+=t[X[j]]*pw;
         }
         ans+=bitset<45>(val).to_string();
      }
      for (int i=0; i<Q; ++i){
         ans+=bitset<9>(p[i]).to_string();
      }
      #ifdef sus
      ofstream out("spy3.out");
      for (int i:T) out << f[i] << ' ';
      out << '\n';
      out.close();
      #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], f[N];
   int t[M], p[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;
         }
      }
   }
   int par[M];
   bool del[M];
   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);
      }
      int cur=0;
      for (int i=0; i<K; i+=11){
         int val=bitset<45>(s.substr(cur, 45)).to_ullong(); cur+=45;
         for (int j=i; j<K && j<i+11; ++j) t[X[j]]=val%17, val/=17;
      }
      for (int i:X) del[i]=1;
      for (int i=0; i<m; ++i) par[i]=m;
      for (int i=0; i<Q; ++i) p[i]=bitset<9>(s.substr(cur, 9)).to_ullong(), cur+=9;
      for (int i=0; i<Q; ++i){
         vector<int> v;
         for (int j:X) if (t[j]==i) v.push_back(j);
         int id=p[i]==K?m:X[p[i]];
         while (id!=m){
            v.push_back(id);
            id=par[id];
         }
         for (int j:X) edge[j].second=inf;
         for (int j:v) edge[j].second=0;
         dijkstra();
         vector<int32_t> path;
         trace(T[i], path); reverse(path.begin(), path.end());
         answer(path);
         int lst=p[i]==K?m:X[p[i]];
         for (int j:path) if (del[j] && t[j]==i){
            par[j]=lst;
            lst=j;
         }
      }
   }
}

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: 100 / 100