제출 #1267236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267236		LucaLucaM	Two Transportations (JOI19_transportations)	C++20	0 / 100	2 ms	1148 KiB

Azer

#include "Azer.h"
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include <iostream>

#define debug(x) #x << " = " << x << '\n'

namespace {
  struct Edge {
    int u, v, c;
    Edge() {}
    Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
    bool operator < (const Edge &other) const {
      return c != other.c? c < other.c : u != other.u? u < other.u : v < other.v;
    };
  };

  const int INF = 1e9 + 100;
  const int logN = 11;
  const int logW = 9;

  std::vector<bool> memory;
  std::vector<int> finalAnswer;
  
  int num_calls = 0;

  void sendInt(int x, int maxBits) {
    for (int i = 0; i < maxBits; i++) {
      num_calls++;
      assert(num_calls <= 55800 + 5);
      SendA(x >> (maxBits - i - 1) & 1);
    }
  }
  
  int receiveInt(int maxBits) {
    int ret = 0;
    while (maxBits--) {
      assert(!memory.empty());
      ret = ret * 2 + memory[0];
      memory.erase(memory.begin());
    }
    return ret;
  }

  void sendEdge(Edge e) {
    sendInt(e.u, logN);
    sendInt(e.v, logN);
    sendInt(e.c, logW);
  }

  Edge receiveEdge() {
    Edge ret;
    ret.u = receiveInt(logN);
    ret.v = receiveInt(logN);
    ret.c = receiveInt(logW);
    return ret;
  }

  int phase;
  int n, A;
  std::vector<std::vector<std::pair<int, int>>> g;
  std::vector<int> U, V, C;
  std::vector<int> dist;
  std::set<int> S;

  Edge findEdge() {
    Edge ret(0, 0, 511);
    for (int u : S) {
      for (auto [v, c] : g[u]) {
        if (!S.count(v)) {
          if (Edge(u, v, c + dist[u]) < ret) {
            ret = Edge(u, v, c + dist[u]);
          }
        }
      }
    }
    // if (S == std::set<int>{0, 1, 3}) {
      // std::cout << " ??????? " << ret.u << ' ' << ret.v << ' ' << ret.c << '\n';
    // } 
    if (ret.u != ret.v) {
      ret.c -= dist[ret.u];
    } 
    return ret;
  }

  void discover1() {
    if ((int) S.size() == n) {
      return;
    }
    auto e = findEdge();
    sendEdge(e);    
  }

  void discover2() {
    assert(phase == 0);
    auto e = findEdge();
    auto e2 = receiveEdge();
    sendEdge(e);

    // std::cout << "AAAA \n";
    // std::cout << "S: ";
    // for (int x : S) {
    //   std::cout << x << ' ';
    // }
    // std::cout << '\n';

    if (e.u == e.v) {
      e.c = 1e9;
    } else {
      e.c += dist[e.u];
    }
    if (e2.u == e2.v) {
      e2.c = 1e9;
    } else {
      e2.c += dist[e2.u];
    }

    // std::cout << e.u << ' ' << e.v << ' ' << e.c << '\n';
    // std::cout << e2.u << ' ' << e2.v << ' ' << e2.c << '\n';

    if (e2 < e) {
      e = e2;
    }
    
    assert(e.c != 1e9);

    // std::cout << "  ! A added " << e.u << ' ' << e.v << ' ' << e.c << '\n';

    S.insert(e.v);
    dist[e.v] = e.c;
    phase = 0;
  }
}  // namespace

void InitA(int n, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  ::S.insert(0);
  ::g.resize(n);

  for (int i = 0; i < A; i++) {
    ::g[U[i]].push_back({V[i], C[i]});
    ::g[V[i]].push_back({U[i], C[i]});
  }
  ::n = n;
  ::A = A;
  ::U = U;
  ::V = V;
  ::C = C;
  ::dist.resize(n, +INF);
  ::phase = 0;
  ::dist[0] = 0;
}

void ReceiveA(bool x) {
  ::memory.push_back(x);
  ::num_calls++;
  assert(::num_calls <= 55800 + 5);
  if ((int) ::memory.size() == ::logN + ::logN + ::logW) {
    discover2();
  }
}

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

Baijan

#include "Baijan.h"
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include <iostream>

#define debug(x) #x << " = " << x << '\n'

namespace {
  struct Edge {
    int u, v, c;
    Edge() {}
    Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
    bool operator < (const Edge &other) const {
      return c != other.c? c < other.c : u != other.u? u < other.u : v < other.v;
    };
  };

  const int INF = 1e9 + 100;
  const int logN = 11;
  const int logW = 9;

  std::vector<bool> memory;
  std::vector<int> finalAnswer;
  
  int num_calls = 0;
  
  void sendInt(int x, int maxBits) {
    for (int i = 0; i < maxBits; i++) {
      num_calls++;
      assert(num_calls <= 55800 + 5);
      SendB(x >> (maxBits - i - 1) & 1);
    }
  }
  
  int receiveInt(int maxBits) {
    int ret = 0;
    while (maxBits--) {
      assert(!memory.empty());
      ret = ret * 2 + memory[0];
      memory.erase(memory.begin());
    }
    return ret;
  }

  void sendEdge(Edge e) {
    sendInt(e.u, logN);
    sendInt(e.v, logN);
    sendInt(e.c, logW);
  }

  Edge receiveEdge() {
    Edge ret;
    ret.u = receiveInt(logN);
    ret.v = receiveInt(logN);
    ret.c = receiveInt(logW);
    return ret;
  }

  int phase;
  int n, A;
  std::vector<std::vector<std::pair<int, int>>> g;
  std::vector<int> U, V, C;
  std::vector<int> dist;
  std::set<int> S;

  Edge findEdge() {
    Edge ret(0, 0, 511);
    for (int u : S) {
      for (auto [v, c] : g[u]) {
        if (!S.count(v)) {
          if (Edge(u, v, c + dist[u]) < ret) {
            ret = Edge(u, v, c + dist[u]);
          }
        }
      }
    }
    if (ret.u != ret.v) {
      ret.c -= dist[ret.u];
    }
    return ret;
  }

  void discover1() {
    assert(phase == 0);
    if ((int) S.size() == n) {
      return;
    }
    auto e = findEdge();
    // std::cout << "B sent " << e.u << ' ' << e.v << ' ' << e.c << '\n';
    sendEdge(e);    
    phase = 1;
  }

  void discover2() {
    assert(phase == 1);
    auto e = findEdge();
    auto e2 = receiveEdge();
    
    // std::cout << "BBBBB \n";
    // std::cout << "S: ";
    // for (int x : S) {
    //   std::cout << x << ' ';
    // }
    // std::cout << '\n';

    assert(S.count(e.u));
    assert(S.count(e2.u));


    // std::cout << e.u << ' ' << e.v << ' ' << e.c << '\n';
    // std::cout << e2.u << ' ' << e2.v << ' ' << e2.c << '\n';
    
    if (e.u == e.v) {
      e.c = 1e9;
    } else {
      e.c += dist[e.u];
    }
    if (e2.u == e2.v) {
      e2.c = 1e9;
    } else {
      e2.c += dist[e2.u];
    }
    
    if (e2 < e) {
      e = e2;
    }

    // std::cout << "  ! B added " << e.u << ' ' << e.v << ' ' << e.c << '\n';

    S.insert(e.v);
    dist[e.v] = e.c;
    phase = 0;
    discover1();
  }
}  // namespace

void InitB(int n, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  ::S.insert(0);
  ::g.resize(n);

  for (int i = 0; i < A; i++) {
    ::g[U[i]].push_back({V[i], C[i]});
    ::g[V[i]].push_back({U[i], C[i]});
  }
  ::n = n;
  ::A = A;
  ::U = U;
  ::V = V;
  ::C = C;
  ::dist.resize(n, +INF);
  ::phase = 0;
  ::dist[0] = 0;
  discover1();
}

void ReceiveB(bool x) {
  ::memory.push_back(x);
  ::num_calls++;
  assert(::num_calls <= 55800 + 5);
  if ((int) ::memory.size() == ::logN + ::logN + ::logW) {
    discover2();
  }
}

• 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