Submission #1313089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313089		altern23	City Mapping (NOI18_citymapping)	C++20	25 / 100	102 ms	20860 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[]) {
      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);
            }
      }
}

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