oj.uz

Submission #668263

# Submission time Handle Problem Language Result Execution time Memory
668263 2022-12-03T12:38:44 Z 600Mihnea City Mapping (NOI18_citymapping) C++17
25 / 100
 89 ms 8856 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge
{
  int a;
  int b;
  ll cost;
};

bool operator < (Edge f, Edge s)
{
  return f.cost < s.cost;
}

void find_roads(int n, int q, int e_a[], int e_b[], int e_w[])
{
  vector<int> t(n + 1);
  iota(t.begin(), t.end(), 0);
  function<int(int)> root = [&] (int a)
  {
    if (t[a] == a)
    {
      return a;
    }
    else
    {
      return t[a] = root(t[a]);
    }
  };
  auto join = [&] (int a, int b)
  {
    t[root(a)] = root(b);
  };
  vector<Edge> edges;
  for (int i = 1; i <= n; i++)
  {
    for (int j = i + 1; j <= n; j++)
    {
      edges.push_back({i, j, get_distance(i, j)});
    }
  }
  sort(edges.begin(), edges.end());
  int top = 0;
  for (auto &it : edges)
  {
    if (root(it.a) != root(it.b))
    {
      e_a[top] = it.a;
      e_b[top] = it.b;
      e_w[top] = it.cost;
      top++;
      assert(top <= n - 1);
      join(it.a, it.b);
    }
  }
  assert(top == n - 1);
  return;

}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8724 KB Correct: 498501 out of 500000 queries used.
2 Correct 75 ms 8728 KB Correct: 499500 out of 500000 queries used.
3 Correct 65 ms 8784 KB Correct: 492528 out of 500000 queries used.
4 Correct 54 ms 8752 KB Correct: 494515 out of 500000 queries used.
5 Correct 70 ms 8760 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8724 KB Correct: 498501 out of 500000 queries used.
2 Correct 75 ms 8728 KB Correct: 499500 out of 500000 queries used.
3 Correct 65 ms 8784 KB Correct: 492528 out of 500000 queries used.
4 Correct 54 ms 8752 KB Correct: 494515 out of 500000 queries used.
5 Correct 70 ms 8760 KB Correct: 498501 out of 500000 queries used.
6 Correct 82 ms 8856 KB Correct: 495510 out of 500000 queries used.
7 Correct 89 ms 8784 KB Correct: 497503 out of 500000 queries used.
8 Correct 86 ms 8712 KB Correct: 497503 out of 500000 queries used.
9 Correct 79 ms 8768 KB Correct: 495510 out of 500000 queries used.
10 Correct 88 ms 8780 KB Correct: 496506 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 852 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 852 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8724 KB Correct: 498501 out of 500000 queries used.
2 Correct 75 ms 8728 KB Correct: 499500 out of 500000 queries used.
3 Correct 65 ms 8784 KB Correct: 492528 out of 500000 queries used.
4 Correct 54 ms 8752 KB Correct: 494515 out of 500000 queries used.
5 Correct 70 ms 8760 KB Correct: 498501 out of 500000 queries used.
6 Correct 82 ms 8856 KB Correct: 495510 out of 500000 queries used.
7 Correct 89 ms 8784 KB Correct: 497503 out of 500000 queries used.
8 Correct 86 ms 8712 KB Correct: 497503 out of 500000 queries used.
9 Correct 79 ms 8768 KB Correct: 495510 out of 500000 queries used.
10 Correct 88 ms 8780 KB Correct: 496506 out of 500000 queries used.
11 Incorrect 2 ms 852 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -