Submission #1313093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313093		altern23	City Mapping (NOI18_citymapping)	C++20	57 / 100	104 ms	20808 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

void find_roads(int N, int Q, int A[], int B[], int W[]) {
      if (Q == 500000) {
            ll ptr = 0;
            ll mt[N + 5][N + 5];
            memset(mt, 0x3f, sizeof(mt));
            
            vector <pair<ll, pair<ll, ll>>> v;

            for (int i = 1; i <= N; i++) {
                  for (int j = 1; j < i; j++) {
                        mt[i][j] = mt[j][i] = get_distance(i, j);
                        v.push_back({mt[i][j], {i, j}});
                  }
            }

            sort(v.begin(), v.end());
            vector <ll> adj[N + 5];
            for (auto [dist, node] : v) {
                  auto [i, j] = node;
                  if (adj[i].size() == 3 || adj[j].size() == 3) continue;
                  bool ok = 1;
                  for (auto x : adj[i]) {
                        ok &= (mt[i][x] + mt[x][j] != dist);
                  }
                  if (ok) {
                        A[ptr] = i, B[ptr] = j, W[ptr] = dist;
                        ptr++;
                        adj[i].push_back(j);
                        adj[j].push_back(i);
                  }
            }
            return;
      }

      vector <pair<ll, ll>> lf, rg;
      vector <pair<ll, ll>> dist;
      for (int i = 2; i <= N; i++) {
            dist.push_back({get_distance(1, i), i});
      }

      sort(dist.begin(), dist.end());
      ll ptr = 0;
      pair<ll, ll> L, R;

      for (auto [val, idx] : dist) {
            if (lf.empty()) {
                  A[ptr] = 1, B[ptr] = idx, W[ptr] = val;
                  L = {idx, val};
                  lf.push_back({idx, val});
                  ptr++;
            }
            else {
                  if (get_distance(L.first, idx) + L.second == val) {
                        A[ptr] = lf.back().first, B[ptr] = idx, W[ptr] = val - lf.back().second;
                        lf.push_back({idx, val});
                        ptr++;
                        continue;
                  }
                  if (rg.empty()) {
                        A[ptr] = 1, B[ptr] = idx, W[ptr] = val;
                        R = {idx, val};
                        rg.push_back({idx, val});
                        ptr++;
                  }
                  else {
                        A[ptr] = rg.back().first, B[ptr] = idx, W[ptr] = val - rg.back().second;
                        rg.push_back({idx, val});
                        ptr++;
                        continue;
                  }
            }
      }
}

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