제출 #1227525

#제출 시각아이디문제언어결과실행 시간메모리
1227525amine_arouaTwo Transportations (JOI19_transportations)C++20
0 / 100
139 ms1120 KiB
#include "Azer.h" #include<bits/stdc++.h> using namespace std; const int INF = 1e9; // (dist , node) -> 20 + 10 = 30 vector<vector<pair<int ,int>>> adj; vector<bool> vis; priority_queue<pair<int ,int> > pq; vector<int> dist , finaldist; int n , a; void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) { n = N; a = A; adj.assign(N , {}); dist.assign(N , INF); finaldist = dist; pq.push({0 , 0}); vis.assign(N , 0); for(int i = 0 ; i < a ; i++) { adj[U[i]].push_back({V[i] , C[i]}); adj[V[i]].push_back({U[i] , C[i]}); } dist[0]=0; finaldist[0] = 0; } vector<int> batch; void code(int a , int b) { for(int i = 0 ;i < 20 ; i++) { int bit = ((a >> i)&1); SendA(bit); } for(int i = 0 ; i < 10 ; i++) { int bit = ((b >> i)&1); SendA(bit); } } void ReceiveA(bool x) { batch.push_back(x); if((int)batch.size() == 30) { vector<pair<int ,int>> cand; // Node from B int d2 = 0 , n2 = 0; for(int i = 0 ; i < 20 ; i++) { d2|=(batch[i]<<i); } for(int i = 0 ;i < 10 ; i++) { n2|=(batch[i + 20]<<i); } batch.clear(); if(n2 < n) { finaldist[n2] = min(finaldist[n2] , d2); cand.push_back({d2 , n2}); } // Node from A int n1 = n , d1 = 0; if(!pq.empty()) { n1 = pq.top().second; d1 = -pq.top().first; pq.pop(); if(!vis[n1]) { vis[n1] = 1; cand.push_back({d1 , n1}); } } if(cand.empty()) { code(d1 , n1); return ; } //process for(auto [d , node] : cand) { assert(d >= 0); for(auto [u , c] : adj[node]) { if(dist[u] > d + c) { dist[u] = d + c; finaldist[u] = min(finaldist[u] , d + c); pq.push({-(d + c), u}); } } } // send Node A to B code(d1 , n1); } } std::vector<int> Answer() { for(int i = 0 ; i < n ; i++) { // assert(finaldist[i] != INF); } return finaldist; }
#include "Baijan.h" #include<bits/stdc++.h> using namespace std; const int INF_ = 1e9; // (dist_ , node) -> 20 + 10 = 30 vector<vector<pair<int ,int>>> adj_; vector<bool> vis_; priority_queue<pair<int ,int> > pq_; vector<int> dist_; int n_ , b_; void code_(int a , int b) { for(int i = 0 ;i < 20 ; i++) { int bit = ((a >> i)&1); SendB(bit); } for(int i = 0 ; i < 10 ; i++) { int bit = ((b >> i)&1); SendB(bit); } } void InitB(int N, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D) { n_ = N; b_ = B; adj_.assign(N , {}); dist_.assign(N , INF_); pq_.push({0 , 0}); vis_.assign(N , 0); for(int i = 0 ; i < b_ ; i++) { adj_[S[i]].push_back({T[i] , D[i]}); adj_[T[i]].push_back({S[i] , D[i]}); } dist_[0]=0; code_(0 , 0); } vector<int> batch_; bool fr = 1; void ReceiveB(bool y) { batch_.push_back(y); if((int)batch_.size() == 30) { vector<pair<int ,int>> cand; // Node from A int d2 = 0 , n2 = 0; for(int i = 0 ; i < 20 ; i++) { d2|=(batch_[i]<<i); } for(int i = 0 ;i < 10 ; i++) { n2|=(batch_[i + 20]<<i); } batch_.clear(); if(n2 < n_) cand.push_back({d2 , n2}); // Node from B int n1 = n_ , d1 = 0; if(!pq_.empty()) { n1 = pq_.top().second; d1 = -pq_.top().first; pq_.pop(); if(!vis_[n1]) { vis_[n1] = 1; cand.push_back({d1 , n1}); } } if(cand.empty()) { if(fr) { fr = 0; for(int i = 0 ; i <n_ ; i++) { code_(dist_[i] , i); } } return; } //process for(auto [d , node] : cand) { assert(d >= 0); for(auto [u , c] : adj_[node]) { if(dist_[u] > d + c) { dist_[u] = d + c; pq_.push({-(d + c) , u}); } } } // send Node B to A code_(d1 , n1); } }
#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...