oj.uz

Submission #1011208

# Submission time Handle Problem Language Result Execution time Memory
1011208 2024-06-30T05:49:13 Z huutuan Spy 3 (JOI24_spy3) C++17
23 / 100
 60 ms 6776 KB 
#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);
}

#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 5604 KB Partially correct
2 Correct 0 ms 1292 KB Output is correct
3 Partially correct 27 ms 5644 KB Partially correct
4 Partially correct 32 ms 5260 KB Partially correct
5 Partially correct 30 ms 5752 KB Partially correct
6 Partially correct 32 ms 5560 KB Partially correct
7 Partially correct 18 ms 5656 KB Partially correct
8 Partially correct 32 ms 5604 KB Partially correct
9 Partially correct 28 ms 5132 KB Partially correct
10 Correct 15 ms 5320 KB Output is correct
11 Partially correct 23 ms 5724 KB Partially correct
12 Correct 33 ms 5556 KB Output is correct
13 Partially correct 28 ms 5652 KB Partially correct
14 Partially correct 31 ms 5848 KB Partially correct
15 Correct 28 ms 5476 KB Output is correct
16 Correct 15 ms 5396 KB Output is correct
17 Partially correct 39 ms 5480 KB Partially correct
18 Partially correct 50 ms 5672 KB Partially correct
19 Partially correct 39 ms 6744 KB Partially correct
20 Partially correct 31 ms 6732 KB Partially correct
21 Partially correct 43 ms 6612 KB Partially correct
22 Partially correct 60 ms 6644 KB Partially correct
23 Partially correct 40 ms 6744 KB Partially correct
24 Partially correct 58 ms 6668 KB Partially correct
25 Partially correct 60 ms 5396 KB Partially correct
26 Partially correct 59 ms 5516 KB Partially correct
27 Correct 1 ms 1292 KB Output is correct
28 Partially correct 24 ms 5808 KB Partially correct
29 Partially correct 21 ms 4240 KB Partially correct
30 Correct 26 ms 5824 KB Output is correct
31 Correct 20 ms 5920 KB Output is correct
32 Partially correct 26 ms 6004 KB Partially correct
33 Correct 28 ms 5652 KB Output is correct
34 Partially correct 25 ms 6052 KB Partially correct
35 Correct 26 ms 6100 KB Output is correct
36 Partially correct 26 ms 5988 KB Partially correct
37 Partially correct 11 ms 3628 KB Partially correct
38 Partially correct 24 ms 4552 KB Partially correct
39 Partially correct 22 ms 4296 KB Partially correct
40 Correct 8 ms 3856 KB Output is correct
41 Partially correct 15 ms 5900 KB Partially correct
42 Partially correct 20 ms 6196 KB Partially correct
43 Correct 35 ms 6464 KB Output is correct
44 Correct 18 ms 6208 KB Output is correct
45 Partially correct 10 ms 3596 KB Partially correct
46 Partially correct 13 ms 4108 KB Partially correct
47 Correct 13 ms 4108 KB Output is correct
48 Correct 0 ms 1292 KB Output is correct
49 Correct 0 ms 1300 KB Output is correct
50 Partially correct 9 ms 5120 KB Partially correct
51 Partially correct 2 ms 1552 KB Partially correct
52 Partially correct 1 ms 1300 KB Partially correct
53 Partially correct 11 ms 5260 KB Partially correct
54 Partially correct 9 ms 3852 KB Partially correct
55 Partially correct 19 ms 4524 KB Partially correct
56 Partially correct 19 ms 6128 KB Partially correct
57 Partially correct 22 ms 6252 KB Partially correct
58 Partially correct 19 ms 5148 KB Partially correct
59 Partially correct 32 ms 6268 KB Partially correct
60 Partially correct 24 ms 6176 KB Partially correct
61 Partially correct 24 ms 6188 KB Partially correct
62 Partially correct 28 ms 6040 KB Partially correct
63 Partially correct 45 ms 6212 KB Partially correct
64 Correct 15 ms 5648 KB Output is correct
65 Partially correct 21 ms 4928 KB Partially correct
66 Partially correct 17 ms 6776 KB Partially correct
67 Partially correct 21 ms 4908 KB Partially correct
68 Partially correct 21 ms 6684 KB Partially correct
69 Correct 0 ms 1292 KB Output is correct
70 Correct 0 ms 1292 KB Output is correct
71 Correct 0 ms 1292 KB Output is correct
72 Partially correct 7 ms 3340 KB Partially correct
73 Partially correct 14 ms 3836 KB Partially correct
74 Partially correct 15 ms 3860 KB Partially correct
75 Correct 8 ms 3860 KB Output is correct
76 Correct 1 ms 1292 KB Output is correct
77 Correct 18 ms 5368 KB Output is correct
78 Partially correct 16 ms 5408 KB Partially correct
79 Correct 19 ms 5396 KB Output is correct
80 Correct 1 ms 1292 KB Output is correct
81 Partially correct 22 ms 5656 KB Partially correct
82 Partially correct 22 ms 5436 KB Partially correct
83 Partially correct 32 ms 5936 KB Partially correct