Submission #692286

#	Time	Username	Problem	Language	Result	Execution time	Memory
692286		horiseun	Two Transportations (JOI19_transportations)	C++17	100 / 100	741 ms	48888 KiB

Azer

#include "Azer.h"
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <algorithm>
using namespace std;

#define f first
#define s second

int n, dc, c, st, sn, re, idx, pr;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<pair<int, int>> adj[2005];
vector<int> dist;
bool seen[2005];

void dijkstra(int curr, int val) {
  val += pr;
  pr = val;
  dist[curr] = val;
  seen[curr] = true;
  dc++;
  if (dc == n) return;
  for (auto [i, w] : adj[curr]) {
    if (dist[curr] + w < dist[i]) {
      dist[i] = dist[curr] + w;
      pq.push({dist[i], i});
    }
  }
  while (!pq.empty() && seen[pq.top().s]) {
    pq.pop();
  }
  if (pq.empty()) sn = 501;
  else sn = pq.top().f - pr;
  for (int i = 8; i >= 0; i--) {
    SendA((sn >> i) & 1);
  }
  if (pq.empty()) idx = 2000;
  else idx = pq.top().s;
}

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
  n = N;
  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.resize(n, 1e9);
  dijkstra(0, 0);
}

void ReceiveA(bool x) {
  if (st == 0) {
    re = (re << 1) + x;
    c++;
    if (c == 9) {
      c = 0;
      if (sn <= re) {
        for (int i = 10; i >= 0; i--) {
          SendA((idx >> i) & 1);
        }
        dijkstra(idx, sn);
        re = 0;
      } else {
        st = 1;
        idx = 0;
      }
    }
  } else {
    idx = (idx << 1) + x;
    c++;
    if (c == 11) {
      c = 0;
      st = 0;
      dijkstra(idx, re);
      re = 0;
    }
  }
}

vector<int> Answer() {
  return dist;
}

Baijan

#include "Baijan.h"
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <algorithm>
using namespace std;

#define f first
#define s second

int n, dc, c, st, sn, re, idx, pr;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<pair<int, int>> adj[2005];
vector<int> dist;
bool seen[2005];

void dijkstra(int curr, int val) {
  val += pr;
  pr = val;
  dist[curr] = val;
  seen[curr] = true;
  dc++;
  if (dc == n) return;
  for (auto [i, w] : adj[curr]) {
    if (dist[curr] + w < dist[i]) {
      dist[i] = dist[curr] + w;
      pq.push({dist[i], i});
    }
  }
  while (!pq.empty() && seen[pq.top().s]) {
    pq.pop();
  }
  if (pq.empty()) sn = 501;
  else sn = pq.top().f - pr;
  for (int i = 8; i >= 0; i--) {
    SendB((sn >> i) & 1);
  }
  if (pq.empty()) idx = 2000;
  else idx = pq.top().s;
}

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
  n = N;
  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.resize(n, 1e9);
  dijkstra(0, 0);
}

void ReceiveB(bool y) {
  if (st == 0) {
    re = (re << 1) + y;
    c++;
    if (c == 9) {
      c = 0;
      if (sn < re) {
        for (int i = 10; i >= 0; i--) {
          SendB((idx >> i) & 1);
        }
        dijkstra(idx, sn);
        re = 0;
      } else {
        st = 1;
        idx = 0;
      }
    }
  } else {
    idx = (idx << 1) + y;
    c++;
    if (c == 11) {
      c = 0;
      st = 0;
      dijkstra(idx, re);
      re = 0;
    }
  }
}

• 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