#include "Azer.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
static const bool debug = 0;
static const int MAXN = 1400;
static const int MAXM = 500000;
static const int MAXL = (MAXN-1) * 500;
static const int MAXLGL = 20;
static queue<bool> RQB;
static int needBits[MAXN+1];
static priority_queue<pii, vector<pii>, greater<pii>> PQ;
static int DP[MAXN];
static bitset<MAXN> chk;
static vector<int> G[MAXN];
static int A[MAXM], B[MAXM], C[MAXM];
static int N, M, K;
static void send(bool x) { SendA(x); }
static void sendVertex(int v) {
//int l = needBits[K+1];
int l = needBits[N];
for(int i = 0; i < l; i++) send(v & (1<<i));
}
static void sendInt(int x) {
int l = MAXLGL;
for(int i = 0; i < l; i++) send(x & (1<<i));
}
static int getInt(int l) {
int ret = 0;
for(int i = 0; i < l; i++) {
if(RQB.front()) ret |= 1 << i;
RQB.pop();
}
return ret;
}
static int getVertex() { return getInt(needBits[N]); }
static int getInt() { return getInt(MAXLGL); }
static int getMinDist() {
for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
return PQ.empty() ? MAXL : PQ.top().first;
}
static void sendInfo() {
if(debug) {
printf("START SENDINFO A\n");
for(int i = 0; i < N; i++) printf("%d ", int(chk[i]));
puts("");
}
if(K == N) return;
for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
if(PQ.empty()) {
if(debug) printf("SENDINFO A 0\n");
sendVertex(0);
return;
}
int dst, idx;
tie(dst, idx) = PQ.top();
sendVertex(idx);
sendInt(dst);
if(debug) printf("SENDINFO A %d %d\n", idx, dst);
}
static void spread(int sidx, int sdst) {
if(K == N) return;
if(debug) printf("SPREAD A : %d %d\n", sidx, sdst);
if(!chk[sidx]) {
chk[sidx] = true;
DP[sidx] = sdst;
K++;
PQ.push({sdst, sidx});
for(int idx, dst; !PQ.empty();) {
tie(dst, idx) = PQ.top();
if(!chk[idx]) break;
PQ.pop();
if(DP[idx] < dst) continue;
for(int e : G[idx]) {
int v = A[e]^B[e]^idx;
int ndst = dst + C[e];
if(DP[v] <= ndst) continue;
DP[v] = ndst;
PQ.push({ndst, v});
}
}
}
if(debug) {
printf("FIN A %d / %d\n", N, K);
for(int i = 0; i < N; i++) printf("%d ", DP[i]);
puts("");
for(int i = 0; i < N; i++) printf("%d ", int(chk[i]));
puts("");
auto V = PQ;
puts("PQ");
for(int a, b; !V.empty(); V.pop()) {
tie(a, b) = V.top();
printf("%d %d\n", a, b);
}
puts("PQ END");
}
sendInfo();
}
static void spreadTop() {
if(debug) {
puts("SPREADTOP A");
auto V = PQ;
puts("PQ");
for(int a, b; !V.empty(); V.pop()) {
tie(a, b) = V.top();
printf("%d %d\n", a, b);
}
puts("PQ END");
}
if(K == N) return;
for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
spread(PQ.top().second, PQ.top().first);
}
static void consider(int sidx, int sdst) {
if(DP[sidx] <= sdst) return;
if(debug) printf("CONSIDER A %d %d\n", sidx, sdst);
priority_queue<pii, vector<pii>, greater<pii>> V;
DP[sidx] = sdst;
V.push({sdst, sidx});
PQ.push({sdst, sidx});
for(int idx, dst; !V.empty();) {
tie(dst, idx) = V.top(); V.pop();
if(DP[idx] < dst) continue;
for(int e : G[idx]) {
int v = A[e]^B[e]^idx;
int ndst = dst + C[e];
if(DP[v] <= ndst) continue;
V.push({ndst, v});
PQ.push({ndst, v});
DP[v] = ndst;
}
}
}
static void init() {
for(int i = 0, s, e;; i++) {
s = 1<<i; e = s<<1;
if(MAXN < s) break;
for(int j = s; j < e && j <= MAXN; j++)
needBits[j] = i;
}
for(int i = 0; i < M; i++) {
G[A[i]].eb(i);
G[B[i]].eb(i);
}
fill(DP, DP+N, MAXL);
spread(0, 0);
}
static bool stayForLen = false;
static int stayIndex;
void ReceiveA(bool x) {
RQB.push(x);
if(stayForLen) {
int l = MAXLGL;
if(sz(RQB) < l) return;
stayForLen = false;
int dst = getInt();
if(debug) printf("GETINFO A %d %d\n", stayIndex, dst);
if(getMinDist() < dst) {
consider(stayIndex, dst);
spreadTop();
return;
}
spread(stayIndex, dst);
return;
}
int l = needBits[N];
if(sz(RQB) == l) {
int v = getVertex();
if(debug) printf("GETINFO A %d\n", v);
if(!v) {
spreadTop();
} else {
stayForLen = true;
stayIndex = v;
}
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
::N = N; ::M = A;
for(int i = 0; i < M; i++) {
::A[i] = U[i];
::B[i] = V[i];
::C[i] = C[i];
}
init();
}
std::vector<int> Answer() {
vector<int> V;
for(int i = 0; i < N; i++)
V.eb(DP[i]);
return V;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
static const bool debug = 0;
static const int MAXN = 1400;
static const int MAXM = 500000;
static const int MAXL = (MAXN-1) * 500;
static const int MAXLGL = 20;
static queue<bool> RQB;
static int needBits[MAXN+1];
static priority_queue<pii, vector<pii>, greater<pii>> PQ;
static int DP[MAXN];
static bitset<MAXN> chk;
static vector<int> G[MAXN];
static int A[MAXM], B[MAXM], C[MAXM];
static int N, M, K;
static void send(bool x) { SendB(x); }
static void sendVertex(int v) {
//int l = needBits[K+1];
int l = needBits[N];
for(int i = 0; i < l; i++) send(v & (1<<i));
}
static void sendInt(int x) {
int l = MAXLGL;
for(int i = 0; i < l; i++) send(x & (1<<i));
}
static int getInt(int l) {
int ret = 0;
for(int i = 0; i < l; i++) {
if(RQB.front()) ret |= 1 << i;
RQB.pop();
}
return ret;
}
static int getVertex() { return getInt(needBits[N]); }
static int getInt() { return getInt(MAXLGL); }
static int getMinDist() {
for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
return PQ.empty() ? MAXL : PQ.top().first;
}
static void sendInfo() {
if(debug) puts("SENDINFO B START");
for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
if(PQ.empty()) {
if(debug) printf("SENDINFO B 0\n");
sendVertex(0);
return;
}
int dst, idx;
tie(dst, idx) = PQ.top();
sendVertex(idx);
sendInt(dst);
if(debug) printf("SENDINFO B %d %d\n", idx, dst);
}
static void spread(int sidx, int sdst, bool ign = false) {
if(debug) printf("SPREAD B %d %d\n", sidx, sdst);
if(!chk[sidx]) {
chk[sidx] = true;
DP[sidx] = sdst;
K++;
PQ.push({sdst, sidx});
for(int idx, dst; !PQ.empty();) {
tie(dst, idx) = PQ.top();
if(!chk[idx]) break;
PQ.pop();
if(DP[idx] < dst) continue;
for(int e : G[idx]) {
int v = A[e]^B[e]^idx;
int ndst = dst + C[e];
if(DP[v] <= ndst) continue;
DP[v] = ndst;
PQ.push({ndst, v});
}
}
}
if(debug) {
puts("FIN B");
for(int i = 0; i < N; i++) printf("%d ", DP[i]);
for(int i = 0; i < N; i++) printf("%d ", int(chk[i]));
puts("");
}
if(!ign) sendInfo();
if(debug) puts("SPREAD B END");
}
static void spreadTop() {
for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
if(!PQ.empty()) spread(PQ.top().second, PQ.top().first);
else sendInfo();
}
static void consider(int sidx, int sdst) {
if(DP[sidx] <= sdst) return;
priority_queue<pii, vector<pii>, greater<pii>> V;
DP[sidx] = sdst;
V.push({sdst, sidx});
PQ.push({sdst, sidx});
for(int idx, dst; !V.empty();) {
tie(dst, idx) = V.top(); V.pop();
if(DP[idx] < dst) continue;
for(int e : G[idx]) {
int v = A[e]^B[e]^idx;
int ndst = dst + C[e];
if(DP[v] <= ndst) continue;
V.push({ndst, v});
PQ.push({ndst, v});
DP[v] = ndst;
}
}
}
static void init() {
for(int i = 0, s, e;; i++) {
s = 1<<i; e = s<<1;
if(MAXN < s) break;
for(int j = s; j < e && j <= MAXN; j++)
needBits[j] = i;
}
for(int i = 0; i < M; i++) {
G[A[i]].eb(i);
G[B[i]].eb(i);
}
fill(DP, DP+N, MAXL);
spread(0, 0, true);
}
static bool stayForLen = false;
static int stayIndex;
void ReceiveB(bool x) {
RQB.push(x);
if(stayForLen) {
int l = MAXLGL;
if(sz(RQB) < l) return;
stayForLen = false;
int dst = getInt();
if(debug) printf("GETINFO B %d %d / %d\n", stayIndex, dst, getMinDist());
if(getMinDist() < dst) {
consider(stayIndex, dst);
spreadTop();
return;
}
spread(stayIndex, dst);
return;
}
int l = needBits[N];
if(sz(RQB) == l) {
int v = getVertex();
if(debug) printf("GETINFO B %d\n", v);
if(!v) {
spreadTop();
} else {
stayForLen = true;
stayIndex = v;
}
}
}
void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
::N = N; ::M = A;
for(int i = 0; i < M; i++) {
::A[i] = U[i];
::B[i] = V[i];
::C[i] = C[i];
}
init();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
1292 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1408 KB |
Output is correct |
2 |
Runtime error |
7 ms |
1264 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
1068 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
566 ms |
752 KB |
Wrong Answer [2] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
566 ms |
752 KB |
Wrong Answer [2] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
566 ms |
752 KB |
Wrong Answer [2] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
1292 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |