| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1224409 | abczz | Spy 3 (JOI24_spy3) | C++20 | 0 ms | 0 KiB |
#include "Aoi.h"
#include <iostream>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long
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) {
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
vector <ll> dist, P, E, virtualP;
string S;
ll missingedge[20000], G[300];
vector <array<ll, 3>> adj[10000];
dist.resize(N);
P.resize(N);
virtualP.resize(K);
E.resize(N);
for (int i=0; i<N; ++i) dist[i] = (ll)1e18, P[i] = -1;
for (int i=0; i<M; ++i) {
missingedge[i] = -1;
adj[A[i]].push_back({B[i], C[i], i});
adj[B[i]].push_back({A[i], C[i], i});
}
for (int i=0; i<K; ++i) G[i] = -1, virtualP[i] = -1;
for (int i=0; i<X.size(); ++i) missingedge[X[i]] = i;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist[u] != w) continue;
for (auto [v, x, id] : adj[u]) {
if (dist[v] > dist[u] + x) {
dist[v] = dist[u] + x;
P[v] = u;
E[v] = id;
pq.push({dist[v], v});
}
}
}
array<ll, 2> cnt[17];
vector <ll> st, pv;
for (int i=0; i<17; ++i) cnt[i] = {0, i};
for (int i=0; i<Q; ++i) {
ll u = T[i];
vector <ll> V;
while (u) {
if (missingedge[E[u]] != -1) {
if (G[missingedge[E[u]]] == -1) G[missingedge[E[u]]] = i;
V.push_back(missingedge[E[u]]);
}
u = P[u];
}
if (V.empty()) st.push_back(-1), pv.push_back(-1);
else {
if (G[V[0]] != i) st.push_back(-1), pv.push_back(V[0]);
if (G[V.back()] == i) st.push_back(V.back()), pv.push_back(-1);
}
for (int j=0; j+1<V.size(); ++j) {
if (G[V[j]] == i && G[V[j+1]] != i) st.push_back(V[j]), pv.push_back(V[j+1]);
if (virtualP[V[j]] == -1) virtualP[V[j]] = V[j+1];
}
}
for (int i=0; i<K; ++i) ++cnt[G[i] == -1 ? 16 : G[i]][0];
sort(cnt, cnt+17, [](auto a, auto b) {
return a[0] < b[0];
});
if (cnt[0][1] > cnt[1][1]) swap(cnt[0], cnt[1]);
for (int i=0; i<2; ++i) {
for (int k=4; k>=0; --k) S += char('0'+min(1LL, cnt[i][1]&(1LL<<k)));
}
for (int i=0; i<K; ++i) {
ll u = G[i] == -1 ? 16 : G[i];
if (u == cnt[0][1]) S += "11110";
else if (u == cnt[1][1]) S += "11111";
else {
if (u >= cnt[1][1]) --u;
if (u >= cnt[0][1]) --u;
for (int k=3; k>=0; --k) S += char('0'+min(1LL, u&(1LL<<k)));
}
}
for (int i=0; i<Q; ++i) {
if (st[i] == -1) S += "111111111";
else {
for (int k=8; k>=0; --k) S += char('0'+min(1LL, st[i]&(1LL<<k)));
}
if (pv[i] == -1) S += "111111111";
else {
for (int k=8; k>=0; --k) S += char('0'+min(1LL, pv[i]&(1LL<<k)));
}
}
return S;
}
#include <algorithm>
#include <csignal>
#include <cstdio>
#include <utility>
#include <vector>
#include <string>
#include "Aoi.h"
#include "Bitaro.h"
namespace {
const int MAX_S_LEN = 12'000;
FILE *u_to_m, *m_to_u;
enum {
ERROR_TESTCASE = -2,
ERROR_WRONG_FORMAT = -1,
ERROR_S_CHAR = 1,
ERROR_S_LENGTH = 2,
ERROR_V_VALUE_RANGE = 3,
ERROR_PATH = 4,
ERROR_DISTANCE = 5,
ERROR_ANSWER_CALL = 6,
};
void wrong(int num) {
fprintf(u_to_m, "%d\n", num);
fflush(u_to_m);
exit(0); // do not exit(1)! (it might cause RE where WA is appropriate)
}
int N, M, Q, K;
std::vector<int> A, B, T, X;
std::vector<long long> C;
std::string s;
int answer_count = 0;
} // namespace
void answer(const std::vector<int> &e) {
for (int t : e) {
if (!(0 <= t && t <= M - 1)) {
wrong(ERROR_V_VALUE_RANGE);
}
}
fprintf(u_to_m, "%zu\n", e.size());
for (int i = 0; i < (int)e.size(); i++) {
fprintf(u_to_m, "%d", e[i]);
if (i != (int)e.size() - 1) {
fprintf(u_to_m, " ");
}
}
fprintf(u_to_m, "\n");
fflush(u_to_m);
}
int main(int argc, char **argv) {
if (argc < 4) {
fprintf(stderr, "Usage: %s <in> <out> <shard>\n", argv[0]);
return 1;
}
// open PIPE
signal(SIGPIPE, SIG_IGN);
u_to_m = fopen(argv[2], "w");
m_to_u = fopen(argv[1], "r");
int shard = atoi(argv[3]);
if (shard == 0) {
// Aoi
if (fscanf(m_to_u, "%d%d", &N, &M) != 2) {
wrong(ERROR_WRONG_FORMAT);
}
A.resize(M);
B.resize(M);
C.resize(M);
for (int i = 0; i < M; i++) {
if (fscanf(m_to_u, "%d%d%lld", &A[i], &B[i], &C[i]) != 3) {
wrong(ERROR_WRONG_FORMAT);
}
}
if (fscanf(m_to_u, "%d", &Q) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
T.resize(Q);
for (int i = 0; i < Q; i++) {
if (fscanf(m_to_u, "%d", &T[i]) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
}
if (fscanf(m_to_u, "%d", &K) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
X.resize(K);
for (int i = 0; i < K; i++) {
if (fscanf(m_to_u, "%d", &X[i]) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
}
s = aoi(N, M, Q, K, A, B, C, T, X);
if (s.length() > MAX_S_LEN) {
wrong(ERROR_S_LENGTH);
}
for (char c : s) {
if (c != '0' && c != '1') {
wrong(ERROR_S_CHAR);
}
}
fprintf(u_to_m, "A");
for (char c : s) {
fprintf(u_to_m, "%c", c);
}
fprintf(u_to_m, "F\n");
fflush(u_to_m);
} else if (shard == 1) {
// Bitaro
if (fscanf(m_to_u, "%d%d", &N, &M) != 2) {
wrong(ERROR_WRONG_FORMAT);
}
A.resize(M);
B.resize(M);
C.resize(M);
for (int i = 0; i < M; i++) {
if (fscanf(m_to_u, "%d%d%lld", &A[i], &B[i], &C[i]) != 3) {
wrong(ERROR_WRONG_FORMAT);
}
}
if (fscanf(m_to_u, "%d", &Q) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
T.resize(Q);
for (int i = 0; i < Q; i++) {
if (fscanf(m_to_u, "%d", &T[i]) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
}
if (fscanf(m_to_u, "%d", &K) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
X.resize(K);
for (int i = 0; i < K; i++) {
if (fscanf(m_to_u, "%d", &X[i]) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
}
char buf;
if (fscanf(m_to_u, " %c", &buf) !=
1) { // 改行を読み飛ばして入力を受け取る
wrong(ERROR_WRONG_FORMAT);
}
if (buf != 'A') {
wrong(ERROR_WRONG_FORMAT);
}
while (true) {
if (fscanf(m_to_u, "%c", &buf) != 1) {
wrong(ERROR_WRONG_FORMAT);
}
if (buf == '0' || buf == '1') {
s.push_back(buf);
if ((int)s.length() > MAX_S_LEN) {
wrong(ERROR_S_LENGTH);
}
} else if (buf == 'F') {
break;
} else {
wrong(ERROR_WRONG_FORMAT);
}
}
bitaro(N, M, Q, K, A, B, C, T, X, s);
fprintf(u_to_m, "F\n");
fflush(u_to_m);
}
return 0;
}