Submission #1227714

#TimeUsernameProblemLanguageResultExecution timeMemory
1227714amine_arouaTwo Transportations (JOI19_transportations)C++20
0 / 100
173 ms13440 KiB
#include "Azer.h" #include<bits/stdc++.h> using namespace std; const int INF = (1<<20) - 1; // (dist , node) -> 20 + 10 = 30 vector<vector<pair<int ,int>>> adj; vector<bool> vis; priority_queue<pair<int ,int>,vector<pair<int ,int>> , greater<pair<int ,int>> > pq; vector<int> dist ; int n , a; int nA = 0 , dA = 0; 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 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); 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; vis[0] = 1; nA = dA = 0; pq.push({0 , 0}); code(0 , 0); } vector<int> batch; pair<int ,int> decode() { int dA = 0 , nA = 0; for(int i = 0 ; i < 20 ; i++) dA|=(batch[i]<<i); for(int i = 0 ;i < 10 ; i++) nA|=(batch[i + 20]<<i); return {dA , nA}; } void upd(int N , int D) { for(auto [u , c] : adj[N]) { if(dist[u] > D + c) { // cout<<u<<'\n'; dist[u] = D + c; pq.push({D + c , u}); } } } void ReceiveA(bool x) { batch.push_back(x); if((int)batch.size() == 30) { auto [dB , nB] = decode(); if(nA == n && nB == n) { return ; } int candN = nA , candD = dA; if(dA > dB) { candN = nB; candD = dB; dist[nB] = dB; } else { pq.pop(); } vis[candN] = 1; // cout<<"A : "<<candN<<" "<<candD<<'\n'; upd(candN , candD); while(!pq.empty() && vis[pq.top().second]) pq.pop(); nA = n , dA = INF; if(!pq.empty()) { nA = pq.top().second; dA = pq.top().first; } // cout<<"d : "<<dA<<" "<<nA<<'\n'; code(dA , nA); batch.clear(); } } std::vector<int> Answer() { for(int i = 0 ; i < n ; i++) { assert(dist[i] != INF); } return dist; }
#include "Baijan.h" #include<bits/stdc++.h> using namespace std; const int INF_ = (1<<20) - 1; // (dist_ , node) -> 20 + 10 = 30 vector<vector<pair<int ,int>>> adj_; vector<bool> vis_; priority_queue<pair<int ,int>,vector<pair<int ,int>> ,greater<pair<int ,int>> > pq_; vector<int> dist_; int n_ , b_; int nB = 0 , dB = 0; 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_); 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; vis_[0] = 0; nB = dB = 0; pq_.push({0 , 0}); code_(0 , 0); } vector<int> batch_; pair<int ,int> decode_() { int dA = 0 , nA = 0; for(int i = 0 ; i < 20 ; i++) dA|=(batch_[i]<<i); for(int i = 0 ;i < 10 ; i++) nA|=(batch_[i + 20]<<i); return {dA , nA}; } void upd_(int N , int D) { for(auto [u , c] : adj_[N]) { if(dist_[u] > D + c) { dist_[u] = D + c; // cout<<"B : "<<u<<'\n'; pq_.push({D + c , u}); } } } void ReceiveB(bool y) { batch_.push_back(y); if((int)batch_.size() == 30) { auto [dA , nA] = decode_(); if(nB == n_ && nA == n_) { return ; } int candN = nB , candD = dB; if(nA == nB) { pq_.pop(); candN = nB; } else { if(dA <= dB) { candN = nA; candD = dA; dist_[nA] = dA; } else { pq_.pop(); } } vis_[candN] = 1; // cout<<"B : "<<candN<<" "<<candD<<'\n'; upd_(candN , candD); while(!pq_.empty() && vis_[pq_.top().second]) pq_.pop(); nB = n_ , dB = INF_; if(!pq_.empty()) { nB = pq_.top().second; dB = pq_.top().first; } // cout<<"NB : "<<nB<<'\n'; code_(dB , nB); batch_.clear(); } }
#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...