Submission #1200999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200999		kim	Two Transportations (JOI19_transportations)	C++20	58 / 100	238 ms	43972 KiB

Azer

#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()

namespace {
  const int inf=1e6+1;
  vector<pii> adj[2005];
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  int d[2005],n,m0,cnt,v0,w0,prv;
  pii prv2;
  bitset<2005> vis;
  void send(bool x){ return SendA(x); }
  void send(int x,int m){ while(m--) send(x&1), x>>=1; }
  void send(pii x){
    if(x==prv2) return void(send(1));
    prv2=x;
    send(0);
    if(x.s==n) send(511,9);
    else send(x.f-prv,9), send(x.s,11);
  }
  void play(){
    if(pq.empty()) return;
    auto [w,u]=pq.top(); pq.pop();
    if(u==n) return;
    if(vis[u]) return play();
    vis[u]=1;
    for(auto &[v,vw]:adj[u]) if(d[v]>w+vw) pq.emplace(d[v]=w+vw,v);
    while(!pq.empty() && pq.top().s!=n && vis[pq.top().s]) pq.pop();
    prv=w;
    send(pq.top());
  }
}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
  n=N;
  for(int i=0;i<A;++i) adj[U[i]].eb(V[i],C[i]), adj[V[i]].eb(U[i],C[i]);
  m0=cnt=0;
  prv2={-1,0};
  fill(d,d+N,inf);
  pq.emplace(inf,N);
  pq.emplace(d[0]=0,0);
  play();
}

void ReceiveA(bool x) {
  if(cnt==0){
    if(x){
      m0=cnt=0;
      play();
      return;
    }
  }
  else if(cnt<10) m0 |= x<<cnt-1;
  else m0 |= x<<cnt-10;
  ++cnt;
  if(cnt==10){
    w0=m0, m0=0;
    if(w0==511){
      cnt=0;
      play();
    }
    else w0+=prv;
  }
  else if(cnt==21){
    v0=m0;
    m0=cnt=0;
    if(d[v0]>w0) pq.emplace(d[v0]=w0,v0);
    play();
  }
}

std::vector<int> Answer() {
  vector<int> ans(n);
  for(int i=0;i<n;++i) ans[i]=d[i];
  return ans;
}

Baijan

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define eb emplace_back
#define sz(x) (int)x.size()
#define f first
#define s second

namespace {
  const int inf=1e6+1;
  vector<pii> adj[2005];
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  int d[2005],n,m0,cnt,v0,w0,prv;
  pii prv2;
  bitset<2005> vis;
  void send(bool x){ return SendB(x); }
  void send(int x,int m){ while(m--) send(x&1), x>>=1; }
  void send(pii x){
    if(x==prv2) return void(send(1));
    prv2=x;
    send(0);
    if(x.s==n) send(511,9);
    else send(x.f-prv,9), send(x.s,11);
  }
  void play(){
    if(pq.empty()) return;
    auto [w,u]=pq.top(); pq.pop();
    if(u==n) return;
    if(vis[u]) return play();
    vis[u]=1;
    for(auto &[v,vw]:adj[u]) if(d[v]>w+vw) pq.emplace(d[v]=w+vw,v);
    while(!pq.empty() && pq.top().s!=n && vis[pq.top().s]) pq.pop();
    prv=w;
    send(pq.top());
  }
}  // namespace

void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
  n=N;
  for(int i=0;i<A;++i) adj[U[i]].eb(V[i],C[i]), adj[V[i]].eb(U[i],C[i]);
  m0=cnt=0;
  prv2={-1,0};
  fill(d,d+N,inf);
  pq.emplace(inf,N);
  pq.emplace(d[0]=0,0);
  play();
}

void ReceiveB(bool x) {
  if(cnt==0){
    if(x){
      m0=cnt=0;
      play();
      return;
    }
  }
  else if(cnt<10) m0 |= x<<cnt-1;
  else m0 |= x<<cnt-10;
  ++cnt;
  if(cnt==10){
    w0=m0, m0=0;
    if(w0==511){
      cnt=0;
      play();
    }
    else w0+=prv;
  }
  else if(cnt==21){
    v0=m0;
    m0=cnt=0;
    if(d[v0]>w0) pq.emplace(d[v0]=w0,v0);
    play();
  }
}

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