Submission #579122

#TimeUsernameProblemLanguageResultExecution timeMemory
579122LucppTwo Transportations (JOI19_transportations)C++17
100 / 100
895 ms48652 KiB
#include "Azer.h" #include <bits/stdc++.h> using namespace std; const int INF = 1e8; namespace { int N; vector<vector<pair<int, int>>> g; vector<int> dist; vector<bool> vis; queue<bool> received; int numRecv; int curDist = 0; int numVisited = 0; int nxt, nxtDist; void sendInt(int x, int bits){ for(int i = 0; i < bits; i++){ bool b = x & (1<<i); SendA(b); } } void visit(int u){ numVisited++; vis[u] = true; curDist = dist[u]; for(auto [v, c] : g[u]){ dist[v] = min(dist[v], dist[u]+c); } if(numVisited == N) return; nxt = -1, nxtDist = INF; for(int i = 0; i < N; i++){ if(!vis[i] && dist[i] < nxtDist){ nxtDist = dist[i]; nxt = i; } } int x = min(nxtDist-curDist, 501); numRecv = 9; sendInt(x, 9); } int receiveInt(int bits){ int ans = 0; for(int i = 0; i < bits; i++){ bool b = received.front(); received.pop(); if(b) ans += (1<<i); } // cerr << "A " << ans << " " << bits << endl; return ans; } void receive(){ if(numRecv == 9){ int x = receiveInt(9); int otherDist = x+curDist; if(otherDist < nxtDist){ nxtDist = otherDist; numRecv = 11; } else{ sendInt(nxt, 11); visit(nxt); } } else if(numRecv == 11){ nxt = receiveInt(11); dist[nxt] = nxtDist; visit(nxt); } } } // namespace void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) { ::N = N; g.resize(N); for (int i = 0; i < A; ++i) { g[U[i]].emplace_back(V[i], C[i]); g[V[i]].emplace_back(U[i], C[i]); } dist.assign(N, INF); dist[0] = 0; vis.resize(N); ::visit(0); } void ReceiveA(bool x) { received.push(x); if((int)received.size() == numRecv){ ::receive(); } } std::vector<int> Answer() { return dist; }
#include "Baijan.h" #include <bits/stdc++.h> using namespace std; const int INF = 1e8; namespace { int N; vector<vector<pair<int, int>>> g; vector<int> dist; vector<bool> vis; queue<bool> received; int numRecv; int curDist = 0; int numVisited = 0; int nxt, nxtDist; void sendInt(int x, int bits){ for(int i = 0; i < bits; i++){ bool b = x & (1<<i); SendB(b); } } void visit(int u){ numVisited++; vis[u] = true; curDist = dist[u]; for(auto [v, c] : g[u]){ dist[v] = min(dist[v], dist[u]+c); } if(numVisited == N) return; nxt = -1, nxtDist = INF; for(int i = 0; i < N; i++){ if(!vis[i] && dist[i] < nxtDist){ nxtDist = dist[i]; nxt = i; } } int x = min(nxtDist-curDist, 501); numRecv = 9; sendInt(x, 9); } int receiveInt(int bits){ int ans = 0; for(int i = 0; i < bits; i++){ bool b = received.front(); received.pop(); if(b) ans += (1<<i); } // cerr << "B " << ans << " " << bits << endl; return ans; } void receive(){ if(numRecv == 9){ int x = receiveInt(9); int otherDist = x+curDist; if(otherDist <= nxtDist){ nxtDist = otherDist; numRecv = 11; } else{ sendInt(nxt, 11); visit(nxt); } } else if(numRecv == 11){ nxt = receiveInt(11); dist[nxt] = nxtDist; visit(nxt); } } } // namespace void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) { ::N = N; g.resize(N); for (int i = 0; i < A; ++i) { g[U[i]].emplace_back(V[i], C[i]); g[V[i]].emplace_back(U[i], C[i]); } dist.assign(N, INF); dist[0] = 0; vis.resize(N); vis[0] = true; ::visit(0); } void ReceiveB(bool x) { received.push(x); if((int)received.size() == numRecv){ ::receive(); } }
#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...