oj.uz

Submission #668362

# Submission time Handle Problem Language Result Execution time Memory
668362 2022-12-03T17:24:16 Z 600Mihnea City Mapping (NOI18_citymapping) C++17
57 / 100
 11 ms 484 KB 
#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};
  vector<vector<int>> g;
  int top = 0;

  auto add_edge = [&] (int a, int b)
  {
    e_a[top] = a + 1;
    e_b[top] = b + 1;
    e_w[top] = dist0[b] - dist0[a];
    top++;
  };
  for (auto &vertex : ord)
  {
    ///dfs(0);
    for (int p = (int) deja.size() - 1; p >= 0; p--)
    {
      int oth = deja[p];
      if (ask(oth, vertex) + dist0[oth] == dist0[vertex])
      {
        add_edge(oth, vertex);
        break;
      }
    }
    deja.push_back(vertex);
  }
  assert(top == n - 1);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2917 out of 500000 queries used.
2 Correct 1 ms 468 KB Correct: 3403 out of 500000 queries used.
3 Correct 4 ms 468 KB Correct: 68207 out of 500000 queries used.
4 Correct 6 ms 340 KB Correct: 117026 out of 500000 queries used.
5 Correct 2 ms 340 KB Correct: 20830 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2917 out of 500000 queries used.
2 Correct 1 ms 468 KB Correct: 3403 out of 500000 queries used.
3 Correct 4 ms 468 KB Correct: 68207 out of 500000 queries used.
4 Correct 6 ms 340 KB Correct: 117026 out of 500000 queries used.
5 Correct 2 ms 340 KB Correct: 20830 out of 500000 queries used.
6 Correct 1 ms 468 KB Correct: 2018 out of 500000 queries used.
7 Correct 11 ms 484 KB Correct: 129256 out of 500000 queries used.
8 Correct 5 ms 468 KB Correct: 68451 out of 500000 queries used.
9 Correct 8 ms 340 KB Correct: 123223 out of 500000 queries used.
10 Correct 2 ms 340 KB Correct: 18028 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2121 out of 12000 queries used.
2 Correct 1 ms 468 KB Correct: 2424 out of 12000 queries used.
3 Correct 1 ms 468 KB Correct: 2629 out of 12000 queries used.
4 Correct 1 ms 468 KB Correct: 2618 out of 12000 queries used.
5 Correct 1 ms 468 KB Correct: 2326 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2121 out of 12000 queries used.
2 Correct 1 ms 468 KB Correct: 2424 out of 12000 queries used.
3 Correct 1 ms 468 KB Correct: 2629 out of 12000 queries used.
4 Correct 1 ms 468 KB Correct: 2618 out of 12000 queries used.
5 Correct 1 ms 468 KB Correct: 2326 out of 12000 queries used.
6 Correct 1 ms 468 KB Correct: 2919 out of 12000 queries used.
7 Correct 1 ms 468 KB Correct: 2755 out of 12000 queries used.
8 Correct 1 ms 468 KB Correct: 2384 out of 12000 queries used.
9 Correct 1 ms 468 KB Correct: 2443 out of 12000 queries used.
10 Correct 1 ms 468 KB Correct: 2618 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 2917 out of 500000 queries used.
2 Correct 1 ms 468 KB Correct: 3403 out of 500000 queries used.
3 Correct 4 ms 468 KB Correct: 68207 out of 500000 queries used.
4 Correct 6 ms 340 KB Correct: 117026 out of 500000 queries used.
5 Correct 2 ms 340 KB Correct: 20830 out of 500000 queries used.
6 Correct 1 ms 468 KB Correct: 2018 out of 500000 queries used.
7 Correct 11 ms 484 KB Correct: 129256 out of 500000 queries used.
8 Correct 5 ms 468 KB Correct: 68451 out of 500000 queries used.
9 Correct 8 ms 340 KB Correct: 123223 out of 500000 queries used.
10 Correct 2 ms 340 KB Correct: 18028 out of 500000 queries used.
11 Correct 1 ms 468 KB Correct: 2121 out of 12000 queries used.
12 Correct 1 ms 468 KB Correct: 2424 out of 12000 queries used.
13 Correct 1 ms 468 KB Correct: 2629 out of 12000 queries used.
14 Correct 1 ms 468 KB Correct: 2618 out of 12000 queries used.
15 Correct 1 ms 468 KB Correct: 2326 out of 12000 queries used.
16 Correct 1 ms 468 KB Correct: 2919 out of 12000 queries used.
17 Correct 1 ms 468 KB Correct: 2755 out of 12000 queries used.
18 Correct 1 ms 468 KB Correct: 2384 out of 12000 queries used.
19 Correct 1 ms 468 KB Correct: 2443 out of 12000 queries used.
20 Correct 1 ms 468 KB Correct: 2618 out of 12000 queries used.
21 Correct 1 ms 468 KB Correct: 2945 out of 25000 queries used.
22 Incorrect 3 ms 468 KB Too many calls to get_distance().
23 Halted 0 ms 0 KB -