Submission #38713543

---

Source Code Expand

#include <bits/stdc++.h>
constexpr int DEBUG = 0;
using namespace std;
using int64 = long long;

constexpr int INF = 1E9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  s << "[";
  for (int i = 0; i < int(v.size()); i++) {
    if (i > 0) {
      s << ", ";
    }
    s << v[i];
  }
  s << "]";
  return s;
}

template<typename T>
vector<vector<T>> Make2D(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}

template<typename T>
vector<vector<vector<T>>>
Make3D(int d1, int d2, int d3, T default_value) {
  return vector<vector<vector<T>>>(
      d1, vector<vector<T>>(d2, vector<T>(d3, default_value)));
}

class Random {
 public:
  Random()
      : random_engine_(
            std::chrono::system_clock::now().time_since_epoch().count()) {}

  Random(int seed) : random_engine_(seed) {}

  int RandomInt(int a, int b, bool inclusive = false) {
    if (inclusive) b++;
    return uniform_int_distribution<int>(a, b - 1)(random_engine_);
  }

  double RandomDouble(double a, double b) {
    return uniform_real_distribution<double>(a, b)(random_engine_);
  }

  template <class T>
  void Shuffle(vector<T>& v) {
    shuffle(v.begin(), v.end(), random_engine_);
  }

 private:
  default_random_engine random_engine_;
};

class TimeMeasurement {
 public:
  TimeMeasurement() : start_(chrono::steady_clock::now()) {}

  int64 CurrentMs() const {
    auto now = chrono::steady_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(now - start_).count();
  }

  int64 CurrentUs() const {
    auto now = chrono::steady_clock::now();
    return chrono::duration_cast<chrono::microseconds>(now - start_).count();
  }

  void Reset() {
    start_ = chrono::steady_clock::now();
  }

 private:
  chrono::time_point<chrono::steady_clock> start_;
};

struct UndirectedEdge {
  int id, v0, v1;
  int w;
  UndirectedEdge(int id, int v0, int v1, int w)
      : id(id), v0(v0), v1(v1), w(w) {}
};
const UndirectedEdge kInvalidUndirectedEdge = UndirectedEdge(-1, -1, -1, 0);

struct Edge {
  int id, s, t;
  int w;
  Edge(int id, int s, int t, int w) : id(id), s(s), t(t), w(w) {}
};
const Edge kInvalidEdge = Edge(-1, -1, -1, 0);

struct CompactEdge {
  int id;
  int t;
  CompactEdge(int id, int t) : id(id), t(t) {}
  CompactEdge() : id(-1), t(-1) {}
};
const CompactEdge kInvalidCompactEdge = CompactEdge(-1, -1);

struct Int2D {
  int x, y;
  Int2D(int x, int y) : x(x), y(y) {}
};

void ShortestPath(
    const vector<vector<Edge>>& graph,
    const vector<int>& is_edge_active, int s,
    vector<int>& distance_vector,
    vector<CompactEdge>& parent_edge_vector) {
  int n = graph.size();
  for (int v = 0; v < n; v++) {
    distance_vector[v] = INF;
    parent_edge_vector[v] = kInvalidCompactEdge;
  }

  vector<int> finalized(n);
  struct S {
    int v;
    int w;
  };
  auto c = [](const S& s1, const S& s2) { return s1.w > s2.w; };
  priority_queue<S, vector<S>, decltype(c)> pq(c);
  distance_vector[s] = 0;
  pq.push(S({s, 0}));
  while (!pq.empty()) {
    S s = pq.top();
    pq.pop();
    if (finalized[s.v]) {
      continue;
    }
    finalized[s.v] = 1;
    for (const auto& e : graph[s.v]) {
      if (!is_edge_active[e.id]) continue;
      if (!finalized[e.t] && s.w + e.w < distance_vector[e.t]) {
        distance_vector[e.t] = s.w + e.w;
        parent_edge_vector[e.t] = CompactEdge(e.id, e.s);
        pq.push(S({e.t, distance_vector[e.t]}));
      }
    }
  }
}

double ShortestPathAverageDeltaWithEdgeAddition(
    const vector<vector<Edge>>& graph, const vector<int>& is_edge_active,
    const UndirectedEdge& added_edge, int s, vector<int>& distance_vector,
    vector<CompactEdge>& parent_edge_vector,
    vector<tuple<int, int, CompactEdge>>& history_tuples) {
  if (distance_vector[added_edge.v0] + added_edge.w >=
          distance_vector[added_edge.v1] &&
      distance_vector[added_edge.v1] + added_edge.w >=
          distance_vector[added_edge.v0]) {
    return 0.0;
  }

  double distance_delta = 0;
  auto update = [&](int v, double d, int edge_id, int p) -> void {
    history_tuples.push_back({v, distance_vector[v], parent_edge_vector[v]});

    distance_delta += d - distance_vector[v];
    distance_vector[v] = d;
    parent_edge_vector[v] = CompactEdge(edge_id, p);
  };

  int r = -1;
  int d_r = 0;
  if (distance_vector[added_edge.v0] + added_edge.w <
      distance_vector[added_edge.v1]) {
    r = added_edge.v1;
    d_r = distance_vector[added_edge.v0] + added_edge.w;
    update(r, d_r, added_edge.id, added_edge.v0);
  } else if (distance_vector[added_edge.v1] + added_edge.w <
             distance_vector[added_edge.v0]) {
    r = added_edge.v0;
    d_r = distance_vector[added_edge.v1] + added_edge.w;
    update(r, d_r, added_edge.id, added_edge.v1);
  } else {
    exit(1);
  }

  constexpr int MAX_VERTEX_COUNT = 1000;
  static vector<int> visited(MAX_VERTEX_COUNT);
  static vector<int> visited_vertex_list;

  struct S {
    int v;
    int w;
  };
  static auto c = [](const S& s1, const S& s2) { return s1.w > s2.w; };
  static priority_queue<S, vector<S>, decltype(c)> pq(c);

  pq.push(S({r, d_r}));
  while (!pq.empty()) {
    // loop_count++;
    S s = pq.top();
    pq.pop();
    if (visited[s.v]) {
      continue;
    }
    visited[s.v] = 1;
    visited_vertex_list.push_back(s.v);
    for (const Edge e : graph[s.v]) {
      if (!is_edge_active[e.id]) continue;
      if (!visited[e.t] && s.w + e.w < distance_vector[e.t]) {
        update(e.t, s.w + e.w, e.id, e.s);
        pq.push(S({e.t, distance_vector[e.t]}));
      }
    }
  }

  // Reset visited and visited_vertex_list for reuse.
  for (int v : visited_vertex_list) {
    visited[v] = 0;
    // finalized_count++;
  }
  visited_vertex_list.clear();

  return distance_delta / (graph.size() - 1);
}

double ShortestPathAverageDeltaWithEdgeDeletion(
    const vector<vector<Edge>>& graph, const vector<int>& is_edge_active,
    const UndirectedEdge& deleted_edge, int s, vector<int>& distance_vector,
    vector<CompactEdge>& parent_edge_vector,
    vector<tuple<int, int, CompactEdge>>& history_tuples) {
  int r = -1;
  if (parent_edge_vector[deleted_edge.v0].t == deleted_edge.v1) {
    r = deleted_edge.v0;
  } else if (parent_edge_vector[deleted_edge.v1].t == deleted_edge.v0) {
    r = deleted_edge.v1;
  } else {
    return 0.0;
  }

  static vector<int> invalidated_vertex_list;
  static deque<int> q;
  invalidated_vertex_list.push_back(r);
  q.push_back(r);
  while (!q.empty()) {
    int v = q.front();
    q.pop_front();
    for (const Edge& e : graph[v]) {
      if (parent_edge_vector[e.t].t == v) {
        invalidated_vertex_list.push_back(e.t);
        q.push_back(e.t);
      }
    }
  };

  constexpr int MAX_VERTEX_COUNT = 1000;
  static vector<int> invalidated(MAX_VERTEX_COUNT);
  for (int v : invalidated_vertex_list) {
    invalidated[v] = 1;
    // invalidated_count++;
  }
  static vector<int> finalized(MAX_VERTEX_COUNT);
  static vector<int> finalized_vertex_list;

  struct S {
    int v;
    int w;
  };
  static auto c = [](const S& s1, const S& s2) { return s1.w > s2.w; };
  static priority_queue<S, vector<S>, decltype(c)> pq(c);

  double distance_delta = 0;
  auto update = [&](int v, int d, int edge_id, int p) -> void {
    history_tuples.push_back({v, distance_vector[v], parent_edge_vector[v]});

    distance_delta += d - distance_vector[v];
    distance_vector[v] = d;
    parent_edge_vector[v] = CompactEdge(edge_id, p);
  };

  for (int v : invalidated_vertex_list) {
    // CompactEdge parent_edge = parent_edge_vector[v];
    int min_d = INF;
    Edge min_edge = kInvalidEdge;
    for (const Edge& e : graph[v]) {
      if (!is_edge_active[e.id]) continue;
      if (!invalidated[e.t]) {
        if (distance_vector[e.t] + e.w < min_d) {
          min_d = distance_vector[e.t] + e.w;
          min_edge = e;
        }
      }
    }

    if (min_edge.id >= 0) {
      invalidated[v] = 0;
      update(v, min_d, min_edge.id, min_edge.t);
      pq.push(S({v, min_d}));
    }
  }

  while (!pq.empty()) {
    S s = pq.top();
    pq.pop();
    if (finalized[s.v]) {
      continue;
    }
    finalized[s.v] = 1;
    finalized_vertex_list.push_back(s.v);
    for (const Edge e : graph[s.v]) {
      if (!is_edge_active[e.id]) continue;
      if (invalidated[e.t]) {
        invalidated[e.t] = 0;
        update(e.t, s.w + e.w, e.id, e.s);
        pq.push(S({e.t, distance_vector[e.t]}));
      } else if (!finalized[e.t] && s.w + e.w < distance_vector[e.t]) {
        update(e.t, s.w + e.w, e.id, e.s);
        pq.push(S({e.t, distance_vector[e.t]}));
      }
    }
  }

  for (int v : invalidated_vertex_list) {
    if (invalidated[v]) {
      update(v, INF, -1, -1);
    }
  }

  // Reset invalidated and invalidated_vertex_list for reuse.
  for (int v : invalidated_vertex_list) {
    invalidated[v] = 0;
  }
  invalidated_vertex_list.clear();

  // Reset finalized and finalized_vertex_list for reuse.
  for (int v : finalized_vertex_list) {
    finalized[v] = 0;
  }
  finalized_vertex_list.clear();

  return distance_delta / (graph.size() - 1);
}

double ExponentialInterpolation(
      double x0, double y0, double x1, double y1, double x) {
  double r = (x - x0) / (x1 - x0);
  return exp(log(y0) + r * (log(y1) - log(y0)));
}

class Main {
 public:
  Main(int vertex_count, int edge_count, int day_count,
       int max_assignment_per_day, const vector<UndirectedEdge>& edges,
       const vector<Int2D>& points)
      : vertex_count_(vertex_count),
        edge_count_(edge_count),
        day_count_(day_count),
        max_assignment_per_day_(max_assignment_per_day),
        edges_(edges),
        points_(points),
        graph_(GraphFromEdges(vertex_count, edges)),
        base_distance_matrix_(
            BaseDistanceMatrix(vertex_count, edge_count, graph_)) {}

  void Run() { RunInternal(); }

 private:
  Random random_ = Random(0);
  TimeMeasurement time_;

  const int vertex_count_;
  const int edge_count_;
  const int day_count_;
  const int max_assignment_per_day_;
  const vector<UndirectedEdge> edges_;
  const vector<Int2D> points_;

  const vector<vector<Edge>> graph_;
  const vector<vector<int>> base_distance_matrix_;

  static vector<vector<Edge>> GraphFromEdges(
      int vertex_count, const vector<UndirectedEdge>& edges) {
    vector<vector<Edge>> graph(vertex_count);
    for (const auto& edge : edges) {
      graph[edge.v0].push_back(Edge(edge.id, edge.v0, edge.v1, edge.w));
      graph[edge.v1].push_back(Edge(edge.id, edge.v1, edge.v0, edge.w));
    }
    return graph;
  }

  static vector<vector<int>> BaseDistanceMatrix(
      int vertex_count,
      int edge_count,
      const vector<vector<Edge>>& graph) {
    vector<vector<int>> base_distance_matrix =
        Make2D(vertex_count, vertex_count, INF);
    vector<vector<CompactEdge>> parent_edge_vectors =
        Make2D(vertex_count, vertex_count, kInvalidCompactEdge);
    for (int s = 0; s < vertex_count; s++) {
      ShortestPath(
          graph, vector<int>(edge_count, 1), s, base_distance_matrix[s],
          parent_edge_vectors[s]);
    }
    return base_distance_matrix;
  }

  vector<int> InitializeEdgeAssignment() {
    vector<int> edge_assignment(edge_count_);
    for (int edge_id = 0; edge_id < edge_count_; edge_id++) {
      edge_assignment[edge_id] = edge_id % day_count_;
    }
    return edge_assignment;
  }

  vector<vector<int>> InitializeDayToIsEdgeActive(
      const vector<int>& edge_assignment) {
    vector<vector<int>> day_to_is_edge_active =
        Make2D(day_count_, edge_count_, 1);
    for (int edge_id = 0; edge_id < edge_count_; edge_id++) {
      day_to_is_edge_active[edge_assignment[edge_id]][edge_id] = 0;
    }
    return day_to_is_edge_active;
  }

  void OutputEdgeAssignment(const vector<int>& edge_assignment) {
    for (int edge_id = 0; edge_id < edge_count_; edge_id++) {
      cout << edge_assignment[edge_id] + 1 << " ";
    }
    cout << endl;
  }

  tuple<vector<int>, vector<double>> MakeSampleVertexes(int grid_size) {
    auto find_closest_vertex = [&](double x, double y) -> int {
      double min_d2 = DBL_MAX;
      int min_d2_v = -1;
      for (int v = 0; v < vertex_count_; v++) {
        double d2 = (points_[v].x - x) * (points_[v].x - x) +
                    (points_[v].y - y) * (points_[v].y - y);
        if (d2 < min_d2) {
          min_d2 = d2;
          min_d2_v = v;
        }
      }
      return min_d2_v;
    };

    vector<int> sample_vs;
    for (int y_index = 0; y_index < grid_size; y_index++) {
      for (int x_index = 0; x_index < grid_size; x_index++) {
        double x = 1000.0 / (2 * grid_size) * (2 * x_index + 1);
        double y = 1000.0 / (2 * grid_size) * (2 * y_index + 1);
        if ((x - 500.0) * (x - 500.0) + (y - 500.0) * (y - 500.0) >
            500.0 * 500.0) {
          continue;
        }
        sample_vs.push_back(find_closest_vertex(x, y));
      }
    }

    vector<double> weights(sample_vs.size());
    for (int v = 0; v < vertex_count_; v++) {
      double d2_min = DBL_MAX;
      int d2_min_sample_id = -1;
      for (int sample_id = 0; sample_id < int(sample_vs.size()); sample_id++) {
        double dx = points_[v].x - points_[sample_vs[sample_id]].x;
        double dy = points_[v].y - points_[sample_vs[sample_id]].y;
        double d2 = dx * dx + dy * dy;
        if (d2 < d2_min) {
          d2_min = d2;
          d2_min_sample_id = sample_id;
        }
      }
      weights[d2_min_sample_id] += 1.0;
    }
    for (int i = 0; i < int(sample_vs.size()); i++) {
      weights[i] /= vertex_count_;
    }

    return {sample_vs, weights};
  }

  void RunMainPhase(
      vector<int>& edge_assignment,
      vector<vector<int>>& day_to_is_edge_active) {
    vector<int> day_to_assignment_count(day_count_);
    for (int edge_id = 0; edge_id < edge_count_; edge_id++) {
      day_to_assignment_count[edge_assignment[edge_id]]++;
    }

    const auto [sample_vs, sample_weights] = MakeSampleVertexes(5);
    int sample_count = sample_vs.size();
    cerr << "sample_count: " << sample_count << endl;

    vector<vector<vector<int>>> day_sample_to_distance_vector =
        Make3D(day_count_, sample_count, vertex_count_, INF);
    vector<vector<vector<CompactEdge>>> day_sample_to_parent_edge_vector =
        Make3D(day_count_, sample_count, vertex_count_, kInvalidCompactEdge);

    for (int day = 0; day < day_count_; day++) {
      for (int sample_id = 0; sample_id < sample_count; sample_id++) {
        int s = sample_vs[sample_id];
        ShortestPath(
            graph_, day_to_is_edge_active[day], s,
            day_sample_to_distance_vector[day][sample_id],
            day_sample_to_parent_edge_vector[day][sample_id]);
      }
    }

    vector<vector<tuple<int, int, CompactEdge>>> sample_to_history_vector_0(
        sample_count);
    vector<vector<tuple<int, int, CompactEdge>>> sample_to_history_vector_1(
        sample_count);

    double sa_start_time = time_.CurrentMs();
    double sa_end_time = 5700.0;
    int try_count = 0;
    int update_count = 0;
    double delta_sum = 0.0;
    while (true) {
      double current_time = time_.CurrentMs();
      if (current_time >= sa_end_time) {
        break;
      }
      constexpr double MAX_TEMPERATURE = 10.0;
      constexpr double MIN_TEMPERATURE = 0.1;
      double temperature = ExponentialInterpolation(
          sa_start_time, MAX_TEMPERATURE, sa_end_time, MIN_TEMPERATURE,
          current_time);

      int edge_id = random_.RandomInt(0, edge_count_);
      int day_0 = edge_assignment[edge_id];
      int day_1 = random_.RandomInt(0, day_count_);
      if (day_0 == day_1) continue;
      if (day_to_assignment_count[day_1] >= max_assignment_per_day_) {
        continue;
      }

      try_count++;

      day_to_is_edge_active[day_0][edge_id] = 1;
      day_to_is_edge_active[day_1][edge_id] = 0;

      double delta = 0;
      for (int sample_id = 0; sample_id < sample_count; sample_id++) {
        int s = sample_vs[sample_id];
        double weight = sample_weights[sample_id];
        delta += ShortestPathAverageDeltaWithEdgeAddition(
                     graph_, day_to_is_edge_active[day_0], edges_[edge_id], s,
                     day_sample_to_distance_vector[day_0][sample_id],
                     day_sample_to_parent_edge_vector[day_0][sample_id],
                     sample_to_history_vector_0[sample_id]) *
                 weight * (1.0 / day_count_);
        delta += ShortestPathAverageDeltaWithEdgeDeletion(
                     graph_, day_to_is_edge_active[day_1], edges_[edge_id], s,
                     day_sample_to_distance_vector[day_1][sample_id],
                     day_sample_to_parent_edge_vector[day_1][sample_id],
                     sample_to_history_vector_1[sample_id]) *
                 weight * (1.0 / day_count_);
      }

      if (exp(-delta / temperature) >= random_.RandomDouble(0, 1)) {
        delta_sum += delta;
        update_count++;
        edge_assignment[edge_id] = day_1;
        day_to_assignment_count[day_0]--;
        day_to_assignment_count[day_1]++;

        for (int sample_id = 0; sample_id < sample_count; sample_id++) {
          sample_to_history_vector_0[sample_id].clear();
          sample_to_history_vector_1[sample_id].clear();
        }
      } else {
        day_to_is_edge_active[day_0][edge_id] = 0;
        day_to_is_edge_active[day_1][edge_id] = 1;
        for (int sample_id = 0; sample_id < sample_count; sample_id++) {
          auto& history_vector_0 = sample_to_history_vector_0[sample_id];
          for (int history_index = history_vector_0.size() - 1;
               history_index >= 0; history_index--) {
            const auto [v, d, e] = history_vector_0[history_index];
            day_sample_to_distance_vector[day_0][sample_id][v] = d;
            day_sample_to_parent_edge_vector[day_0][sample_id][v] = e;
          }
          history_vector_0.clear();

          auto& history_vector_1 = sample_to_history_vector_1[sample_id];
          for (int history_index = history_vector_1.size() - 1;
               history_index >= 0; history_index--) {
            const auto [v, d, e] = history_vector_1[history_index];
            day_sample_to_distance_vector[day_1][sample_id][v] = d;
            day_sample_to_parent_edge_vector[day_1][sample_id][v] = e;
          }
          history_vector_1.clear();
        }
      }

      if (try_count % 10000 == 0) {
        cerr << "try_count: " << try_count << endl;
        cerr << "update_count: " << update_count << endl;
        cerr << "delta_sum: " << delta_sum << endl;
      }
    }
    cerr << "try_count: " << try_count << endl;
    cerr << "update_count: " << update_count << endl;
    cerr << "delta_sum: " << delta_sum << endl;
  }

  void RunInternal() {
    vector<int> edge_assignment = InitializeEdgeAssignment();

    vector<vector<int>> day_to_is_edge_active =
        InitializeDayToIsEdgeActive(edge_assignment);
    
    RunMainPhase(edge_assignment, day_to_is_edge_active);

    OutputEdgeAssignment(edge_assignment);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int vertex_count;
  cin >> vertex_count;
  int edge_count;
  cin >> edge_count;
  int day_count;
  cin >> day_count;
  int max_assignment_per_day;
  cin >> max_assignment_per_day;

  vector<UndirectedEdge> edges;
  for (int edge_id = 0; edge_id < edge_count; edge_id++) {
    int v0, v1;
    int w;
    cin >> v0 >> v1 >> w;
    v0--;
    v1--;
    edges.push_back(UndirectedEdge(edge_id, v0, v1, w));
  }

  vector<Int2D> points;
  for (int vertex_id = 0; vertex_id < vertex_count; vertex_id++) {
    int x, y;
    cin >> x >> y;
    points.push_back(Int2D(x, y));
  }

  Main main(vertex_count, edge_count, day_count, max_assignment_per_day, edges, points);
  main.Run();
}

Submission Info

Compile Error

./Main.cpp: In function ‘double ShortestPathAverageDeltaWithEdgeAddition(const std::vector<std::vector<Edge> >&, const std::vector<int>&, const UndirectedEdge&, int, std::vector<int>&, std::vector<CompactEdge>&, std::vector<std::tuple<int, int, CompactEdge> >&)’:
./Main.cpp:149:43: warning: unused parameter ‘s’ [-Wunused-parameter]
  149 |     const UndirectedEdge& added_edge, int s, vector<int>& distance_vector,
      |                                       ~~~~^
./Main.cpp: In function ‘double ShortestPathAverageDeltaWithEdgeDeletion(const std::vector<std::vector<Edge> >&, const std::vector<int>&, const UndirectedEdge&, int, std::vector<int>&, std::vector<CompactEdge>&, std::vector<std::tuple<int, int, CompactEdge> >&)’:
./Main.cpp:226:45: warning: unused parameter ‘s’ [-Wunused-parameter]
  226 |     const UndirectedEdge& deleted_edge, int s, vector<int>& distance_vector,
      |                                         ~~~~^

Judge Result