Submission #1244687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244687		urosk	Two Transportations (JOI19_transportations)	C++20	0 / 100	173 ms	13444 KiB

Azer

#include "Azer.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 1000000000 // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = long double;
using ll = int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;

static const ll maxn = 2005;
static const ll lgn = 11;
static const ll lgd = 9;
static ll n;
static vector<pll> g[maxn];
static ll dis[maxn];
static bool upd[maxn];

static void dajk(ll u){
  priority_queue<pll> pq;
  pq.push({-dis[u],u});
  while(si(pq)){
    ll d = -pq.top().fi,u = pq.top().sc; pq.pop();
    if(dis[u]!=d) continue;
    for(pll p : g[u]){
      ll s = p.fi,w = p.sc;
      if(dis[s]>dis[u]+w){
        dis[s] = dis[u] + w;
        pq.push({-dis[s],s});
        upd[s] = 1;
      }
    }
  }
}
static void senduj(ll u){
  // cerr<<"SA: ";
  // dbg(u);
  for(ll j = 0;j<lgn;j++){
    if((1<<j)&u) SendA(1);
    else SendA(0);
  }
  for(ll j = 0;j<lgn+lgd;j++){
    if((1<<j)&dis[u]) SendA(1);
    else SendA(0);
  }
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
  n = N;
  for(ll i = 0;i<A;i++){
    ll x = U[i],y = V[i],w = C[i];
    x++; y++;
    g[x].pb({y,w});
    g[y].pb({x,w});
  }
  for(ll i = 1;i<=n;i++) dis[i] = llinf;
  dis[1] = 0;
  dajk(1);
  // ceri(dis,1,n);
  senduj(1);
}
static ll cnt = 0;
static vector<bool> cur;
static pll conv(){
  ll u = 0,disu = 0;
  for(ll j = 0;j<lgn;j++){
    u+=(1<<j)*cur[j];
  }
  for(ll j = lgn;j<lgn*2+lgd;j++){
    disu+=(1<<(j-lgn))*cur[j];
  }
  return {u,disu};
}
void ReceiveA(bool x) {
  cur.pb(x); cnt++;
  if(cnt!=lgn*2+lgd) return;
  pll p = conv();
  cur.clear();
  cnt = 0;
  ll u = p.fi;
  dis[u] = min(dis[u],p.sc);
  dajk(u);
  ll rez = -1;
  for(ll i = 1;i<=n;i++){
    if(!upd[i]) continue;
    if(rez==-1||dis[i]<dis[rez]) rez = i;
  }
  // cerr<<"A: "<<endl;
  // ceri(dis,1,n);
  // ceri(upd,1,n);
  // dbg(rez);
  if(rez==-1){
    senduj(1);
    return;
  }
  upd[rez] = 0;
  senduj(rez);
}

std::vector<int> Answer() {
  vector<ll> ans;
  for(ll i = 1;i<=n;i++) ans.pb(dis[i]);
  for(ll i = 1;i<=n;i++) assert(dis[i]!=llinf);
  // cer(ans);
  return ans;
}

Baijan

#include "Baijan.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 1000000000 // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = long double;
using ll = int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;

static const ll maxn = 2005;
static const ll lgn = 11;
static const ll lgd = 9;
static ll n;
static vector<pll> g[maxn];
static ll dis[maxn];
static bool upd[maxn];

static void dajk(ll u){
  priority_queue<pll> pq;
  pq.push({-dis[u],u});
  while(si(pq)){
    ll d = -pq.top().fi,u = pq.top().sc; pq.pop();
    if(dis[u]!=d) continue;
    for(pll p : g[u]){
      ll s = p.fi,w = p.sc;
      if(dis[s]>dis[u]+w){
        dis[s] = dis[u] + w;
        pq.push({-dis[s],s});
        upd[s] = 1;
      }
    }
  }
}
static void senduj(ll u){
  // cerr<<"SB: ";
  // dbg(u);
  for(ll j = 0;j<lgn;j++){
    if((1<<j)&u) SendB(1);
    else SendB(0);
  }
  for(ll j = 0;j<lgn+lgd;j++){
    if((1<<j)&dis[u]) SendB(1);
    else SendB(0);
  }
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
  n = N;
  for(ll i = 0;i<B;i++){
    ll x = S[i],y = T[i],w = D[i];
    x++; y++;
    g[x].pb({y,w});
    g[y].pb({x,w});
  }
  for(ll i = 1;i<=n;i++) dis[i] = llinf;
  dis[1] = 0;
  dajk(1);
}
static ll cnt = 0;
static vector<bool> cur;
static pll conv(){
  ll u = 0,disu = 0;
  for(ll j = 0;j<lgn;j++){
    u+=(1<<j)*cur[j];
  }
  for(ll j = lgn;j<lgn*2+lgd;j++){
    disu+=(1<<(j-lgn))*cur[j];
  }
  return {u,disu};
}
void ReceiveB(bool y) {
  cur.pb(y); cnt++;
  if(cnt!=lgn*2+lgd) return;
  pll p = conv();
  cur.clear();
  cnt = 0;
  ll u = p.fi;
  dis[u] = min(dis[u],p.sc);
  dajk(u);
  ll rez = -1;
  for(ll i = 1;i<=n;i++){
    if(!upd[i]) continue;
    if(rez==-1||dis[i]<dis[rez]) rez = i;
  }
  // cerr<<"B: "<<endl;
  // ceri(dis,1,n);
  // ceri(upd,1,n);
  // dbg(rez);
  if(rez==-1) return;
  upd[rez] = 0;
  senduj(rez);
}

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