제출 #1012787

#제출 시각아이디문제언어결과실행 시간메모리
1012787huutuanSpy 3 (JOI24_spy3)C++17
23 / 100
58 ms6560 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; } 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], 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); }
#Verdict Execution timeMemoryGrader output
Fetching results...