Submission #1011208

#TimeUsernameProblemLanguageResultExecution timeMemory
1011208huutuanSpy 3 (JOI24_spy3)C++17
23 / 100
60 ms6776 KiB
#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 (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;
      |                                                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...