Submission #132779

#TimeUsernameProblemLanguageResultExecution timeMemory
132779sebinkimTwo Transportations (JOI19_transportations)C++14
68 / 100
1952 ms85384 KiB
#include <bits/stdc++.h> #include "Azer.h" using namespace std; typedef pair <int, int> pii; const int ID = 11; const int DIST = 9; namespace{ priority_queue <pii> Q; vector <pii> G[2020]; vector <int> D; bool chk[2020]; int v, c, t, f = 1234567890, b; int n, z, m; bool turn() { b = (b + 1) % 30; return (f & (1 << b)) != 0; } void sendint(int x, int l) { x = min(x, (1 << l) - 1); for(; l--; ){ SendA((x & (1 << l))? 1 : 0); } } void check() { int p, d; for(; !Q.empty(); Q.pop()){ tie(d, p) = Q.top(); d = -d; if(!chk[p] && d == D[p]) break; } if(Q.empty()) return; tie(d, p) = Q.top(); d = -d; sendint(p, ID); sendint(d - z, DIST); } void apply(int p, int d) { chk[p] = 1; D[p] = d; z = d; for(pii &t: G[p]){ if(!chk[t.first] && D[t.first] > d + t.second){ D[t.first] = d + t.second; Q.emplace(-d - t.second, t.first); } } if(turn()){ m = 1; check(); } else m = 2; } void check(int p1, int d1) { int p, d, p2, d2; for(; !Q.empty(); Q.pop()){ tie(d2, p2) = Q.top(); d2 = -d2; if(!chk[p2] && D[p2] == d2) break; } tie(d2, p2) = Q.top(); d2 = -d2; if(d1 < d2){ p = p1, d = d1; SendA(0); } else{ p = p2, d = d2; Q.pop(); SendA(1); sendint(p, ID); sendint(d - z, DIST); } apply(p, d); } } void InitA(int N, int A, vector <int> U, vector <int> V, vector<int> C) { n = N; D.resize(n, 0); int i; for(i=0; i<A; i++){ G[U[i]].emplace_back(V[i], C[i]); G[V[i]].emplace_back(U[i], C[i]); } for(i=1; i<n; i++){ D[i] = 1e9; } for(i=0; i<n; i++){ Q.emplace(-D[i], i); } apply(0, 0); } void ReceiveA(bool x) { if(m == 1){ if(t == 0){ if(!x){ int d, p; tie(d, p) = Q.top(); d = -d; Q.pop(); apply(p, d); } else t = 1; } else{ v = v << 1 | x; c ++; if(c == ID + DIST){ int p = v >> DIST; int d = z + (v & ((1 << DIST) - 1)); v = 0; c = 0; t = 0; apply(p, d); } } } else{ v = v << 1 | x; c ++; if(c == ID + DIST){ int p = v >> DIST; int d = z + (v & ((1 << DIST) - 1)); v = 0; c = 0; check(p, d); } } } vector <int> Answer() { return D; }
#include <bits/stdc++.h> #include "Baijan.h" using namespace std; typedef pair <int, int> pii; const int ID = 11; const int DIST = 9; namespace{ priority_queue <pii> Q; vector <pii> G[2020]; vector <int> D; bool chk[2020]; int v, c, t, f = 1234567890, b; int n, z, m; bool turn() { b = (b + 1) % 30; return (f & (1 << b)) != 0; } void sendint(int x, int l) { x = min(x, (1 << l) - 1); for(; l--; ){ SendB((x & (1 << l))? 1 : 0); } } void check() { int p, d; for(; !Q.empty(); Q.pop()){ tie(d, p) = Q.top(); d = -d; if(!chk[p] && d == D[p]) break; } if(Q.empty()) return; tie(d, p) = Q.top(); d = -d; sendint(p, ID); sendint(d - z, DIST); } void apply(int p, int d) { chk[p] = 1; D[p] = d; z = d; for(pii &t: G[p]){ if(!chk[t.first] && D[t.first] > d + t.second){ D[t.first] = d + t.second; Q.emplace(-d - t.second, t.first); } } if(!turn()){ m = 1; check(); } else m = 2; } void check(int p1, int d1) { int p, d, p2, d2; for(; !Q.empty(); Q.pop()){ tie(d2, p2) = Q.top(); d2 = -d2; if(!chk[p2] && D[p2] == d2) break; } tie(d2, p2) = Q.top(); d2 = -d2; if(d1 < d2){ p = p1, d = d1; SendB(0); } else{ p = p2, d = d2; Q.pop(); SendB(1); sendint(p, ID); sendint(d - z, DIST); } apply(p, d); } } void InitB(int N, int B, vector <int> S, vector<int> T, vector<int> C) { n = N; D.resize(n, 0); int i; for(i=0; i<B; i++){ G[S[i]].emplace_back(T[i], C[i]); G[T[i]].emplace_back(S[i], C[i]); } for(i=1; i<n; i++){ D[i] = 1e9; } for(i=0; i<n; i++){ Q.emplace(-D[i], i); } apply(0, 0); } void ReceiveB(bool y) { if(m == 1){ if(t == 0){ if(!y){ int d, p; tie(d, p) = Q.top(); d = -d; Q.pop(); apply(p, d); } else t = 1; } else{ v = v << 1 | y; c ++; if(c == ID + DIST){ int p = v >> DIST; int d = z + (v & ((1 << DIST) - 1)); v = 0; c = 0; t = 0; apply(p, d); } } } else{ v = v << 1 | y; c ++; if(c == ID + DIST){ int p = v >> DIST; int d = z + (v & ((1 << DIST) - 1)); v = 0; c = 0; check(p, d); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...