oj.uz

Submission #668384

# Submission time Handle Problem Language Result Execution time Memory
668384 2022-12-03T18:21:03 Z 600Mihnea City Mapping (NOI18_citymapping) C++17
100 / 100
 20 ms 852 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

map<pair<int, int>, ll> mp;

ll ask(int i, int j)
{
  if (i == j)
  {
    return 0;
  }
  if (i > j)
  {
    swap(i, j);
  }
  if (!mp.count({i, j}))
  {
    mp[{i, j}] = get_distance(i + 1, j + 1);
  }
  return mp[{i, j}];
}

void find_roads(int n, int q, int e_a[], int e_b[], int e_w[])
{
  int root = 0;
  vector<ll> dist0(n, 0);
  vector<int> ord;
  for (int i = 0; i < n; i++)
  {
    if (root == i)
    {
      dist0[i] = 0;
      continue;
    }
    dist0[i] = ask(root, 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(n);
  vector<int> sub(n), big(n), u(n), par(n);
  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];
    g[a].push_back(b);
    top++;
  };

  function<void(int)> dfs = [&] (int a)
  {
    sub[a] = 1;
    if (g[a].empty())
    {
      u[a] = a;
      return;
    }
    big[a] = g[a][0];
    for (auto &b : g[a])
    {
      dfs(b);
      par[b] = a;
      sub[a] += sub[b];
      if (sub[b] > sub[big[a]])
      {
        big[a] = b;
      }
    }
    u[a] = u[big[a]];
  };

  function<void(int, int)> locate = [&] (int root, int new_vertex)
  {
    if (sub[root] == 1)
    {
      add_edge(root, new_vertex);
      return;
    }
    int b = u[root];
    ll dist_b_v = ask(b, new_vertex);
    ll dist_b_r = dist0[b] - dist0[root];
    ll dist_v_r = dist0[new_vertex] - dist0[root];
    ll sum_dub = (dist_b_v + dist_b_r + dist_v_r);
    ll sum = sum_dub / 2;
    ll z = sum - dist_b_r;
    ll x = sum - dist_b_v;
    ll y = sum - dist_v_r;
    int fix_inainte = -1;
    if (y == 0)
    {
      add_edge(b, new_vertex);
      return;
    }
    while (y > 0)
    {
      y -= (dist0[b] - dist0[par[b]]);
      fix_inainte = b;
      b = par[b];
    }
    int mid_point = b;
    if (z == 0)
    {
      add_edge(mid_point, new_vertex);
      return;
    }
    if ((int) g[mid_point].size() == 1)
    {
      add_edge(mid_point, new_vertex);
      return;
    }
    vector<int> oth;
    for (auto &vecin : g[mid_point])
    {
      if (vecin == fix_inainte)
      {
        continue;
      }
      oth.push_back(vecin);
    }
    if ((int) oth.size() == 1)
    {
      if (dist0[oth[0]] - dist0[mid_point] >= z)
      {
        add_edge(mid_point, new_vertex);
        return;
      }
      if (ask(u[oth[0]], new_vertex) == z + dist0[u[oth[0]]] - dist0[mid_point])
      {
        add_edge(mid_point, new_vertex);
        return;
      }
      locate(oth[0], new_vertex);
      return;
    }
    if (ask(oth[0], new_vertex) < ask(oth[1], new_vertex))
    {
      locate(oth[0], new_vertex);
    }
    else
    {
      locate(oth[1], new_vertex);
    }
  };

  for (auto &vertex : ord)
  {
    dfs(root);
    locate(root, vertex);
  }
}

Compilation message

citymapping.cpp: In lambda function:
citymapping.cpp:93:8: warning: unused variable 'x' [-Wunused-variable]
   93 |     ll x = sum - dist_b_v;
      |        ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 644 KB Correct: 2695 out of 500000 queries used.
2 Correct 15 ms 596 KB Correct: 2428 out of 500000 queries used.
3 Correct 19 ms 724 KB Correct: 4527 out of 500000 queries used.
4 Correct 19 ms 852 KB Correct: 5523 out of 500000 queries used.
5 Correct 20 ms 716 KB Correct: 3397 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 644 KB Correct: 2695 out of 500000 queries used.
2 Correct 15 ms 596 KB Correct: 2428 out of 500000 queries used.
3 Correct 19 ms 724 KB Correct: 4527 out of 500000 queries used.
4 Correct 19 ms 852 KB Correct: 5523 out of 500000 queries used.
5 Correct 20 ms 716 KB Correct: 3397 out of 500000 queries used.
6 Correct 17 ms 656 KB Correct: 2009 out of 500000 queries used.
7 Correct 17 ms 596 KB Correct: 2063 out of 500000 queries used.
8 Correct 19 ms 728 KB Correct: 4244 out of 500000 queries used.
9 Correct 19 ms 748 KB Correct: 5089 out of 500000 queries used.
10 Correct 19 ms 596 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 680 KB Correct: 2082 out of 12000 queries used.
2 Correct 18 ms 660 KB Correct: 2321 out of 12000 queries used.
3 Correct 19 ms 672 KB Correct: 2459 out of 12000 queries used.
4 Correct 19 ms 724 KB Correct: 2466 out of 12000 queries used.
5 Correct 18 ms 680 KB Correct: 2232 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 680 KB Correct: 2082 out of 12000 queries used.
2 Correct 18 ms 660 KB Correct: 2321 out of 12000 queries used.
3 Correct 19 ms 672 KB Correct: 2459 out of 12000 queries used.
4 Correct 19 ms 724 KB Correct: 2466 out of 12000 queries used.
5 Correct 18 ms 680 KB Correct: 2232 out of 12000 queries used.
6 Correct 20 ms 616 KB Correct: 2473 out of 12000 queries used.
7 Correct 19 ms 672 KB Correct: 2382 out of 12000 queries used.
8 Correct 18 ms 724 KB Correct: 2207 out of 12000 queries used.
9 Correct 18 ms 724 KB Correct: 2235 out of 12000 queries used.
10 Correct 19 ms 700 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 644 KB Correct: 2695 out of 500000 queries used.
2 Correct 15 ms 596 KB Correct: 2428 out of 500000 queries used.
3 Correct 19 ms 724 KB Correct: 4527 out of 500000 queries used.
4 Correct 19 ms 852 KB Correct: 5523 out of 500000 queries used.
5 Correct 20 ms 716 KB Correct: 3397 out of 500000 queries used.
6 Correct 17 ms 656 KB Correct: 2009 out of 500000 queries used.
7 Correct 17 ms 596 KB Correct: 2063 out of 500000 queries used.
8 Correct 19 ms 728 KB Correct: 4244 out of 500000 queries used.
9 Correct 19 ms 748 KB Correct: 5089 out of 500000 queries used.
10 Correct 19 ms 596 KB Correct: 3054 out of 500000 queries used.
11 Correct 17 ms 680 KB Correct: 2082 out of 12000 queries used.
12 Correct 18 ms 660 KB Correct: 2321 out of 12000 queries used.
13 Correct 19 ms 672 KB Correct: 2459 out of 12000 queries used.
14 Correct 19 ms 724 KB Correct: 2466 out of 12000 queries used.
15 Correct 18 ms 680 KB Correct: 2232 out of 12000 queries used.
16 Correct 20 ms 616 KB Correct: 2473 out of 12000 queries used.
17 Correct 19 ms 672 KB Correct: 2382 out of 12000 queries used.
18 Correct 18 ms 724 KB Correct: 2207 out of 12000 queries used.
19 Correct 18 ms 724 KB Correct: 2235 out of 12000 queries used.
20 Correct 19 ms 700 KB Correct: 2302 out of 12000 queries used.
21 Correct 20 ms 700 KB Correct: 2502 out of 25000 queries used.
22 Correct 18 ms 664 KB Correct: 2149 out of 25000 queries used.
23 Correct 17 ms 596 KB Correct: 2592 out of 25000 queries used.
24 Correct 17 ms 664 KB Correct: 2088 out of 25000 queries used.
25 Correct 19 ms 792 KB Correct: 4569 out of 25000 queries used.
26 Correct 19 ms 712 KB Correct: 4358 out of 25000 queries used.
27 Correct 18 ms 700 KB Correct: 4342 out of 25000 queries used.
28 Correct 18 ms 740 KB Correct: 4417 out of 25000 queries used.
29 Correct 19 ms 680 KB Correct: 4502 out of 25000 queries used.
30 Correct 18 ms 712 KB Correct: 4442 out of 25000 queries used.
31 Correct 19 ms 744 KB Correct: 5151 out of 25000 queries used.
32 Correct 15 ms 708 KB Correct: 2223 out of 25000 queries used.
33 Correct 19 ms 768 KB Correct: 5083 out of 25000 queries used.
34 Correct 20 ms 800 KB Correct: 5164 out of 25000 queries used.
35 Correct 18 ms 748 KB Correct: 5100 out of 25000 queries used.
36 Correct 19 ms 724 KB Correct: 5118 out of 25000 queries used.
37 Correct 18 ms 724 KB Correct: 5144 out of 25000 queries used.
38 Correct 18 ms 820 KB Correct: 5102 out of 25000 queries used.
39 Correct 18 ms 724 KB Correct: 5168 out of 25000 queries used.
40 Correct 18 ms 780 KB Correct: 5168 out of 25000 queries used.
41 Correct 19 ms 724 KB Correct: 5124 out of 25000 queries used.
42 Correct 18 ms 820 KB Correct: 5203 out of 25000 queries used.
43 Correct 17 ms 672 KB Correct: 2087 out of 25000 queries used.
44 Correct 18 ms 724 KB Correct: 5116 out of 25000 queries used.
45 Correct 18 ms 736 KB Correct: 5096 out of 25000 queries used.
46 Correct 18 ms 772 KB Correct: 5068 out of 25000 queries used.
47 Correct 18 ms 796 KB Correct: 5179 out of 25000 queries used.
48 Correct 19 ms 724 KB Correct: 5135 out of 25000 queries used.
49 Correct 18 ms 724 KB Correct: 5091 out of 25000 queries used.
50 Correct 19 ms 744 KB Correct: 5105 out of 25000 queries used.
51 Correct 18 ms 724 KB Correct: 5099 out of 25000 queries used.
52 Correct 19 ms 764 KB Correct: 5148 out of 25000 queries used.
53 Correct 18 ms 816 KB Correct: 5144 out of 25000 queries used.
54 Correct 18 ms 636 KB Correct: 2641 out of 25000 queries used.
55 Correct 18 ms 812 KB Correct: 5197 out of 25000 queries used.
56 Correct 20 ms 824 KB Correct: 5141 out of 25000 queries used.
57 Correct 18 ms 820 KB Correct: 5125 out of 25000 queries used.
58 Correct 18 ms 724 KB Correct: 5115 out of 25000 queries used.
59 Correct 18 ms 780 KB Correct: 5109 out of 25000 queries used.
60 Correct 19 ms 628 KB Correct: 3041 out of 25000 queries used.
61 Correct 19 ms 656 KB Correct: 3317 out of 25000 queries used.
62 Correct 19 ms 596 KB Correct: 2917 out of 25000 queries used.
63 Correct 19 ms 692 KB Correct: 3317 out of 25000 queries used.
64 Correct 19 ms 656 KB Correct: 3103 out of 25000 queries used.
65 Correct 17 ms 652 KB Correct: 2145 out of 25000 queries used.
66 Correct 19 ms 724 KB Correct: 3228 out of 25000 queries used.
67 Correct 17 ms 596 KB Correct: 2042 out of 25000 queries used.
68 Correct 19 ms 624 KB Correct: 2786 out of 25000 queries used.
69 Correct 18 ms 596 KB Correct: 2451 out of 25000 queries used.
70 Correct 18 ms 644 KB Correct: 2414 out of 25000 queries used.