Submission #936052

#	Time	Username	Problem	Language	Result	Execution time	Memory
936052		huutuan	Two Transportations (JOI19_transportations)	C++14	100 / 100	622 ms	49040 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

namespace Azer{
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   const int N=2010;
   int f[N], n, vis[N];
   vector<pair<int, int>> g[N];
   int buffer;
   int buffer_size;
   int waiting_size;
   int last_value;
   int remain;
   int ceil_log2(){
      return 32-__builtin_clz(remain);
   }
   int find_idx(int u){
      int ans=0;
      for (int i=0; i<u; ++i) ans+=!vis[i];
      return ans;
   }
   int find_node(int idx){
      int ans=0;
      while (idx>=(!vis[ans])) idx-=!vis[ans], ++ans;
      return ans;
   }
   void FakeSendA(int size, int data){
      for (int i=size-1; i>=0; --i) SendA(data>>i&1);
   }
   void adjust_pq(){
      while (pq.size() && vis[pq.top().second]) pq.pop();
   }
   void reset_buffer(){
      buffer=0;
      buffer_size=0;
   }
   void optimize(int _u=-1, int _f=-1){
      --remain;
      int u=-1;
      if (_u==-1){
         last_value=pq.top().first;
         u=pq.top().second; pq.pop();
      }else{
         last_value=_f;
         u=_u; f[u]=_f;
      }
      vis[u]=1;
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         if (f[v]>f[u]+w) pq.emplace(f[v]=f[u]+w, v);
      }
      adjust_pq();
   }
}

void InitA(int N, int A, vector<int> U, vector<int> V,
           vector<int> C) {
   Azer::n=N;
   Azer::remain=N;
   for (int i=0; i<A; ++i) Azer::g[U[i]].emplace_back(V[i], C[i]), Azer::g[V[i]].emplace_back(U[i], C[i]);
   Azer::pq.emplace(Azer::f[0]=0, 0);
   for (int i=1; i<N; ++i) Azer::pq.emplace(Azer::f[i]=(1<<20)-1, i);
   if (Azer::pq.size()){
      Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first));
      Azer::waiting_size=1;
   }
}

void ReceiveA(bool x) {
   ++Azer::buffer_size;
   Azer::buffer<<=1; Azer::buffer|=x;
   if (Azer::buffer_size==Azer::waiting_size){
      if (Azer::waiting_size==1){
         if (Azer::buffer==0){
            Azer::FakeSendA(Azer::ceil_log2(), Azer::find_idx(Azer::pq.top().second));
            Azer::optimize();
            if (Azer::pq.size()){
               Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first-Azer::last_value));
               Azer::waiting_size=1;
            }
         }else{
            Azer::waiting_size=9+Azer::ceil_log2();
         }
      }else{
         int v=Azer::find_node(Azer::buffer&((1<<Azer::ceil_log2())-1)), f=(Azer::buffer>>Azer::ceil_log2())+Azer::last_value;
         Azer::optimize(v, f);
         if (Azer::pq.size()){
            Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first-Azer::last_value));
            Azer::waiting_size=1;
         }
      }
      Azer::reset_buffer();
   }
}

vector<int> Answer() {
   return vector<int>(Azer::f, Azer::f+Azer::n);
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

namespace Baijan{
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   const int N=2010;
   int f[N], n, vis[N];
   vector<pair<int, int>> g[N];
   int buffer;
   int buffer_size;
   int waiting_size;
   int last_value;
   int remain;
   int ceil_log2(){
      return 32-__builtin_clz(remain);
   }
   int find_idx(int u){
      int ans=0;
      for (int i=0; i<u; ++i) ans+=!vis[i];
      return ans;
   }
   int find_node(int idx){
      int ans=0;
      while (idx>=(!vis[ans])) idx-=!vis[ans], ++ans;
      return ans;
   }
   void FakeSendB(int size, int data){
      for (int i=size-1; i>=0; --i) SendB(data>>i&1);
   }
   void adjust_pq(){
      while (pq.size() && vis[pq.top().second]) pq.pop();
   }
   void reset_buffer(){
      buffer=0;
      buffer_size=0;
   }
   void optimize(int _u=-1, int _f=-1){
      --remain;
      int u=-1;
      if (_u==-1){
         last_value=pq.top().first;
         u=pq.top().second; pq.pop();
      }else{
         last_value=_f;
         u=_u; f[u]=_f;
      }
      vis[u]=1;
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         if (f[v]>f[u]+w) pq.emplace(f[v]=f[u]+w, v);
      }
      adjust_pq();
   }
}

void InitB(int N, int B, vector<int> S, vector<int> T,
           vector<int> D) {
   Baijan::n=N;
   Baijan::remain=N;
   memset(Baijan::f, 0x3f, sizeof Baijan::f);
   for (int i=0; i<B; ++i) Baijan::g[S[i]].emplace_back(T[i], D[i]), Baijan::g[T[i]].emplace_back(S[i], D[i]);
   Baijan::pq.emplace(Baijan::f[0]=0, 0);
   for (int i=1; i<N; ++i) Baijan::pq.emplace(Baijan::f[i]=(1<<20)-1, i);
   Baijan::waiting_size=9;
}

void ReceiveB(bool y) {
   ++Baijan::buffer_size;
   Baijan::buffer<<=1; Baijan::buffer|=y;
   if (Baijan::buffer_size==Baijan::waiting_size){
      if (Baijan::waiting_size==9){
         int fa=Baijan::buffer+Baijan::last_value;
         if (fa<=Baijan::pq.top().first){
            Baijan::FakeSendB(1, 0);
            Baijan::waiting_size+=Baijan::ceil_log2();
            if (Baijan::ceil_log2()==0){
               int v=Baijan::find_node(Baijan::buffer&((1<<Baijan::ceil_log2())-1)), f=(Baijan::buffer>>Baijan::ceil_log2())+Baijan::last_value;
               Baijan::optimize(v, f);
               Baijan::waiting_size=9;
               Baijan::reset_buffer();
            }
         }else{
            Baijan::FakeSendB(1, 1);
            Baijan::FakeSendB(9+Baijan::ceil_log2(), (Baijan::pq.top().first==((1<<20)-1)?511:Baijan::pq.top().first-Baijan::last_value)<<Baijan::ceil_log2()|Baijan::find_idx(Baijan::pq.top().second));
            if (Baijan::pq.size()) Baijan::optimize();
            Baijan::waiting_size=9;
            Baijan::reset_buffer();
         }
      }else{
         int v=Baijan::find_node(Baijan::buffer&((1<<Baijan::ceil_log2())-1)), f=(Baijan::buffer>>Baijan::ceil_log2())+Baijan::last_value;
         Baijan::optimize(v, f);
         Baijan::waiting_size=9;
         Baijan::reset_buffer();
      }
   }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16