Submission #668360

#	Time	Username	Problem	Language	Result	Execution time	Memory
668360		600Mihnea	City Mapping (NOI18_citymapping)	C++17	57 / 100	11 ms	500 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll ask(int i, int j)
{
  return get_distance(i + 1, j + 1);
}

void find_roads(int n, int q, int e_a[], int e_b[], int e_w[])
{
  vector<ll> dist0(n, 0);
  vector<int> ord;
  for (int i = 1; i < n; i++)
  {
    dist0[i] = ask(0, i);
    ord.push_back(i);
  }
  sort(ord.begin(), ord.end(), [&] (int i, int j) {return dist0[i] < dist0[j];});
  vector<int> deja = {0};
  int top = 0;
  for (auto &vertex : ord)
  {
    for (int p = (int) deja.size() - 1; p >= 0; p--)
    {
      int oth = deja[p];
      if (ask(oth, vertex) + dist0[oth] == dist0[vertex])
      {
        e_a[top] = oth + 1;
        e_b[top] = vertex + 1;
        e_w[top] = dist0[vertex] - dist0[oth];
        top++;
        break;
      }
    }
    deja.push_back(vertex);
  }
  if (0)
  {
    for (int i = 0; i < top; i++)
    {
      cout << " : " << e_a[i] << " " << e_b[i] << " " << e_w[i] << "\n";
    }
  }
  assert(top == n - 1);
	return;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 0 / 43