Submission #1235206

#TimeUsernameProblemLanguageResultExecution timeMemory
1235206chaeryeongSpy 3 (JOI24_spy3)C++20
23 / 100
554 ms5744 KiB
#include "Aoi.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; std::string aoi(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<ll> C, std::vector<int> T, std::vector<int> X) { //Lmao how did I not notice the Q sort(X.begin(), X.end()); vector <pair <ll, ll>> adj[N]; vector <int> bad(M, 0); for (auto i : X) { bad[i] = 1; } map <pair <int, int>, int> mp; for (int i = 0; i < M; i++) { adj[A[i]].push_back({B[i], C[i]}); adj[B[i]].push_back({A[i], C[i]}); mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i; } vector <ll> dist(N, (ll)1e18); dist[0] = 0; priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq; pq.push({0, 0}); vector <int> par(N, -1); while (!pq.empty()) { auto [d, node] = pq.top(); pq.pop(); if (d > dist[node]) { continue; } for (auto [j, w] : adj[node]) { if (dist[j] > w + d) { dist[j] = w + d; pq.push({dist[j], j}); par[j] = node; } } } string s; for (int i = 0; i < Q; i++) { int u = T[i]; //cout << u << '\n'; vector <int> path; while (u != -1) { path.push_back(u); u = par[u]; } /* for (auto i : path) { cout << i << " "; } cout << '\n';*/ vector <int> useful(M, 0); for (int j = 0; j + 1 < (int)path.size(); j++) { if (bad[mp[{path[j], path[j + 1]}]]) { useful[mp[{path[j], path[j + 1]}]] = 1; } } for (int j = 0; j < M; j++) { if (bad[j]) { s += (char)(useful[j] + '0'); } } } // cout << s << '\n'; return s; }
#include "Bitaro.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X, std::string s) { sort(X.begin(), X.end()); map <pair <int, int>, int> mp; vector <int> bad(M, 0); for (auto i : X) { bad[i] = 1; } vector <pair <ll, ll>> adj[N]; for (int i = 0; i < M; i++) { mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i; if (!bad[i]) { adj[A[i]].push_back({B[i], C[i]}); adj[B[i]].push_back({A[i], C[i]}); } } assert(s.length() == Q * K); for (int i = 0; i < Q; i++) { vector <int> used(K, 0); for (int j = i * K; j < (i + 1) * K; j++) { used[j - i * K] = s[j] - '0'; } int u = T[i]; // cout << u << '\n'; /* for (auto j : used) { cout << j << " "; } cout << '\n';*/ vector <int> path; while (true) { vector <ll> dist(N, (ll)1e18); assert(u != -1); dist[u] = 0; priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq; pq.push({dist[u], u}); vector <int> par(N, -1); while (!pq.empty()) { auto [d, node] = pq.top(); pq.pop(); if (d > dist[node]) { continue; } for (auto [j, w] : adj[node]) { if (dist[j] > d + w) { dist[j] = d + w; par[j] = node; pq.push({dist[j], j}); } } } int pos = 0, d = -1; for (int i = 0; i < K; i++) { if (!used[i]) { continue; } if (used[i] && dist[A[X[i]]] < dist[pos]) { pos = A[X[i]]; d = i; } if (used[i] && dist[B[X[i]]] < dist[pos]) { pos = B[X[i]]; d = i; } } assert(u != -1); /* cout << u << " " << pos << " " << d << '\n'; for (int i = 0; i < N; i++) { cout << par[i] << " "; } cout << '\n';*/ int t = pos; vector <int> g; while (u != t) { g.push_back(mp[{t, par[t]}]); t = par[t]; if (t == -1) { break; } } reverse(g.begin(), g.end()); for (auto j : g) { path.push_back(j); } if (u == -1) { exit(0); } if (d == -1 || d >= K) { break; } u = pos; path.push_back(X[d]); if (u == A[X[d]]) { u = B[X[d]]; } else { u = A[X[d]]; } used[d] = 0; } reverse(path.begin(), path.end()); /* for (auto i : path) { cout << A[i] << " " << B[i] << '\n'; }*/ answer(path); } }
#Verdict Execution timeMemoryGrader output
Fetching results...