| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1050787 |
2024-08-09T14:30:03 Z |
fuad27 |
Spy 3 (JOI24_spy3) |
C++17 |
|
7 ms |
2584 KB |
#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
std::string aoi(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) {
vector<vector<int>> g(N);
for(int i = 0;i<M;i++) {
g[A[i]].push_back(i);
g[B[i]].push_back(i);
}
vector<long long> dist(N, (long long)1e18);
vector<int> pr(N, -1);
dist[0] = 0;
priority_queue<pair<long long, int>> pq;
pq.push({0, 0});
vector<int> bad_edge(M);
for(auto i=0;i<X.size();i++)bad_edge[X[i]]=i+1;
vector<bool> vis(N);
while(pq.size()) {
int at = pq.top().second;
pq.pop();
if(vis[at])continue;
vis[at]=1;
for(int idx:g[at]) {
int to = (at^A[idx]^B[idx]);
long long w = C[idx];
if(dist[to] > dist[at] + w) {
dist[to] = dist[at] + w;
pr[to] = idx;
pq.push(pair<long long, int>(-dist[to], to));
}
}
}
vector<int> par_final(K+Q);
for(int iii = 0;iii<Q;iii++) {
int cur = pr[T[iii]];
int prev = iii+K;
bool fl=0;
while(1) {
if(fl) {
if(dist[A[cur]] < dist[B[cur]]) {
cur = pr[A[cur]];
}
else cur = pr[B[cur]];
}
fl=1;
if(cur == -1 or bad_edge[cur]) {
if(cur != -1) {
par_final[prev] = bad_edge[cur]-1;
}
else {
par_final[prev] = -1;
}
prev = bad_edge[cur]-1;
}
if(cur == -1)break;
}
}
string res = "";
for(int i = 0;i<Q+K;i++) {
par_final[i]++;
for(int j = 0;j<10;j++) {
if(par_final[i]&(1<<j))res+="1";
else res+="0";
}
}
return res;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
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) {
vector<int> par(K+Q);
for(int i = 0;i<K+Q;i++) {
for(int j = 0;j<10;j++) {
if(s[i*10 + j] == '1')par[i]|=(1<<j);
}
par[i]--;
}
map<pair<int,int>, int> mp;
for(int i = 0;i<N;i++) {
mp[{A[i], B[i]}]=i;
mp[{B[i], A[i]}]=i;
}
for(int st = 0;st<Q;st++) {
for(int idx:X) {
C[idx] = 1e18;
}
{
int at = par[st+K];
while(at!=-1) {
C[X[at]] = 0;
at = par[at];
}
}
vector<vector<pair<int, long long>>> g(N);
for(int i = 0;i<N;i++) {
g[A[i]].push_back({B[i], C[i]});
g[B[i]].push_back({A[i], C[i]});
}
priority_queue<pair<long long, int>> pq;
vector<long long> dist(N, 1e18);
vector<int> pr(N, -1);
vector<bool> vis(N,0);
dist[0] =0 ;
pq.push({0, 0});
while(pq.size()) {
int at = pq.top().second;
pq.pop();
if(vis[at])continue;
for(auto [to,w]:g[at]) {
if(dist[to] > dist[at] + w) {
pr[to] = at;
dist[to] = dist[at]+w;
pq.push({-dist[to], to});
}
}
}
int cur=T[st];
vector<int> ans;
while(pr[cur]!=-1) {
ans.push_back(mp[{pr[cur], cur}]);
cur=pr[cur];
}
reverse(ans.begin(), ans.end());
answer(ans);
}
}
Compilation message
Aoi.cpp: In function 'std::string aoi(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>)':
Aoi.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(auto i=0;i<X.size();i++)bad_edge[X[i]]=i+1;
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2584 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
