oj.uz

Submission #668377

# Submission time Handle Problem Language Result Execution time Memory
668377 2022-12-03T17:59:07 Z 600Mihnea City Mapping (NOI18_citymapping) C++17
88.22 / 100
 18 ms 596 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(n);
  vector<int> sub(n), big(n), u(n), par(n);
  int top = 0;

  auto add_edge = [&] (int a, int b)
  {
 ///   cout << " add_edge : " << a << " " << b << "\n";
    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;
    }
    assert(!g[a].empty());
    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;
    }
    assert(!g[root].empty());
    int b = u[root];
    assert(b != 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];

    /**

    x + y = dist_b_r
    z + y = dist_b_v
    x + z = dist_v_r


    z = sum - dist_b_r
    x = sum - dist_b_v
    y - sum - dist_v_r

    **/

    ll sum_dub = (dist_b_v + dist_b_r + dist_v_r);
    assert(sum_dub % 2 == 0);
    ll sum = sum_dub / 2;

    ll z = sum - dist_b_r;
    ll x = sum - dist_b_v;
    ll y = sum - dist_v_r;

    assert(x + y + z == sum);
    assert(0 <= x);
    assert(0 <= y);
    assert(0 <= z);

    assert(x + y == dist_b_r);
    assert(z + y == dist_b_v);
    assert(x + z == dist_v_r);

    int fix_inainte = -1;

    /// scapa de astea!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   /// assert(x + y == ask(root, b));
   /// assert(x + z == ask(root, new_vertex));
   /// assert(z + y == ask(b, new_vertex));
    /// scapa de astea!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

    if (y == 0)
    {
      add_edge(b, new_vertex);
      return;
    }

   // cout << "x = " << x << "\n";
   // cout << "y = " << y << "\n";
   // cout << "z = " << z << "\n";

    while (y > 0)
    {
      assert(b != root);
      y -= (dist0[b] - dist0[par[b]]);
      fix_inainte = b;
      b = par[b];
    }
    assert(y == 0);

    int mid_point = b;

    if (z == 0)
    {
      add_edge(mid_point, new_vertex);
      return;
    }
    assert(z > 0);
    ///cout << " = " << fix_inainte << " " << b << " " << root << "\n";
    assert(0 <= fix_inainte && fix_inainte < n);
    assert(par[fix_inainte] == b);

    if ((int) g[mid_point].size() == 1)
    {
      add_edge(mid_point, new_vertex);
      return;
    }

    assert((int) g[mid_point].size() == 2 || (int) g[mid_point].size() == 3);
    vector<int> oth;
    for (auto &vecin : g[mid_point])
    {
      if (vecin == fix_inainte)
      {
        continue;
      }
      oth.push_back(vecin);
    }
    assert((int) oth.size() == 1 || (int) oth.size() == 2);
    assert((int) oth.size() == (int) g[mid_point].size() - 1);
    if ((int) oth.size() == 1)
    {
      if (ask(oth[0], new_vertex) < z)
      {
        locate(oth[0], new_vertex);
        return;
      }
      add_edge(mid_point, new_vertex);
      return;
    }
    assert((int) oth.size() == 2);
    if (ask(oth[0], new_vertex) < ask(oth[1], new_vertex))
    {
      locate(oth[0], new_vertex);
    }
    else
    {
      locate(oth[1], new_vertex);
    }
  };

  int nd = 0;

  for (auto &vertex : ord)
  {
    //cout << " \t\t\t\t\t vertex = " << vertex << "\n";

    dfs(0);
    locate(0, vertex);

    nd++;
    assert(nd == top);
    //cout << " \t\t\t\t\t\t\t\t\t" << e_a[nd - 1] - 1 << " " << e_b[nd - 1] - 1 << " " << e_w[nd - 1] << "\n";

    continue;
    int mifa = -1;


    for (int p = (int) deja.size() - 1; p >= 0; p--)
    {
      int oth = deja[p];
      if (ask(oth, vertex) + dist0[oth] == dist0[vertex])
      {
        mifa = oth;
        break;
      }
    }
    if (mifa != e_a[nd - 1] - 1)
    {
      cout << "bad : " << top << "\n";
      cout << "I connected it to " << e_a[nd - 1] - 1 << "\n";
      cout << "The real guy is   " << mifa << "\n";
      exit(0);
    }
    deja.push_back(vertex);
  }
  if (0)
  {
    for (int i = 0; i < top; i++)
    {
      cout << " : " << e_a[i] << " " << e_b[i] << " " << e_w[i] << "\n";
    }
  }
  assert(top == n - 1);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Correct: 3393 out of 500000 queries used.
2 Correct 17 ms 524 KB Correct: 2592 out of 500000 queries used.
3 Correct 16 ms 500 KB Correct: 6716 out of 500000 queries used.
4 Correct 15 ms 496 KB Correct: 8682 out of 500000 queries used.
5 Correct 17 ms 468 KB Correct: 4747 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Correct: 3393 out of 500000 queries used.
2 Correct 17 ms 524 KB Correct: 2592 out of 500000 queries used.
3 Correct 16 ms 500 KB Correct: 6716 out of 500000 queries used.
4 Correct 15 ms 496 KB Correct: 8682 out of 500000 queries used.
5 Correct 17 ms 468 KB Correct: 4747 out of 500000 queries used.
6 Correct 16 ms 596 KB Correct: 2027 out of 500000 queries used.
7 Correct 16 ms 468 KB Correct: 2132 out of 500000 queries used.
8 Correct 16 ms 504 KB Correct: 6197 out of 500000 queries used.
9 Correct 13 ms 468 KB Correct: 7891 out of 500000 queries used.
10 Correct 17 ms 504 KB Correct: 4081 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Correct: 2184 out of 12000 queries used.
2 Correct 16 ms 468 KB Correct: 2657 out of 12000 queries used.
3 Correct 17 ms 468 KB Correct: 2919 out of 12000 queries used.
4 Correct 16 ms 572 KB Correct: 2947 out of 12000 queries used.
5 Correct 17 ms 564 KB Correct: 2484 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Correct: 2184 out of 12000 queries used.
2 Correct 16 ms 468 KB Correct: 2657 out of 12000 queries used.
3 Correct 17 ms 468 KB Correct: 2919 out of 12000 queries used.
4 Correct 16 ms 572 KB Correct: 2947 out of 12000 queries used.
5 Correct 17 ms 564 KB Correct: 2484 out of 12000 queries used.
6 Correct 17 ms 548 KB Correct: 2952 out of 12000 queries used.
7 Correct 17 ms 560 KB Correct: 2774 out of 12000 queries used.
8 Correct 16 ms 568 KB Correct: 2416 out of 12000 queries used.
9 Correct 15 ms 596 KB Correct: 2478 out of 12000 queries used.
10 Correct 16 ms 556 KB Correct: 2618 out of 12000 queries used.

Subtask #5
31.22 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Correct: 3393 out of 500000 queries used.
2 Correct 17 ms 524 KB Correct: 2592 out of 500000 queries used.
3 Correct 16 ms 500 KB Correct: 6716 out of 500000 queries used.
4 Correct 15 ms 496 KB Correct: 8682 out of 500000 queries used.
5 Correct 17 ms 468 KB Correct: 4747 out of 500000 queries used.
6 Correct 16 ms 596 KB Correct: 2027 out of 500000 queries used.
7 Correct 16 ms 468 KB Correct: 2132 out of 500000 queries used.
8 Correct 16 ms 504 KB Correct: 6197 out of 500000 queries used.
9 Correct 13 ms 468 KB Correct: 7891 out of 500000 queries used.
10 Correct 17 ms 504 KB Correct: 4081 out of 500000 queries used.
11 Correct 16 ms 596 KB Correct: 2184 out of 12000 queries used.
12 Correct 16 ms 468 KB Correct: 2657 out of 12000 queries used.
13 Correct 17 ms 468 KB Correct: 2919 out of 12000 queries used.
14 Correct 16 ms 572 KB Correct: 2947 out of 12000 queries used.
15 Correct 17 ms 564 KB Correct: 2484 out of 12000 queries used.
16 Correct 17 ms 548 KB Correct: 2952 out of 12000 queries used.
17 Correct 17 ms 560 KB Correct: 2774 out of 12000 queries used.
18 Correct 16 ms 568 KB Correct: 2416 out of 12000 queries used.
19 Correct 15 ms 596 KB Correct: 2478 out of 12000 queries used.
20 Correct 16 ms 556 KB Correct: 2618 out of 12000 queries used.
21 Correct 17 ms 468 KB Correct: 3013 out of 25000 queries used.
22 Correct 16 ms 468 KB Correct: 2183 out of 25000 queries used.
23 Correct 16 ms 552 KB Correct: 2737 out of 25000 queries used.
24 Correct 16 ms 560 KB Correct: 2115 out of 25000 queries used.
25 Correct 17 ms 468 KB Correct: 6618 out of 25000 queries used.
26 Correct 16 ms 468 KB Correct: 6436 out of 25000 queries used.
27 Correct 17 ms 520 KB Correct: 6349 out of 25000 queries used.
28 Correct 16 ms 524 KB Correct: 6530 out of 25000 queries used.
29 Correct 16 ms 472 KB Correct: 6709 out of 25000 queries used.
30 Correct 16 ms 524 KB Correct: 6602 out of 25000 queries used.
31 Correct 16 ms 468 KB Correct: 7997 out of 25000 queries used.
32 Correct 16 ms 596 KB Correct: 2457 out of 25000 queries used.
33 Correct 15 ms 468 KB Correct: 7877 out of 25000 queries used.
34 Correct 15 ms 468 KB Correct: 8025 out of 25000 queries used.
35 Correct 16 ms 468 KB Correct: 7913 out of 25000 queries used.
36 Correct 15 ms 468 KB Correct: 7945 out of 25000 queries used.
37 Correct 16 ms 468 KB Correct: 8010 out of 25000 queries used.
38 Correct 15 ms 528 KB Correct: 7926 out of 25000 queries used.
39 Correct 16 ms 464 KB Correct: 7958 out of 25000 queries used.
40 Correct 14 ms 512 KB Correct: 8034 out of 25000 queries used.
41 Correct 16 ms 512 KB Correct: 7961 out of 25000 queries used.
42 Correct 15 ms 524 KB Correct: 8109 out of 25000 queries used.
43 Correct 16 ms 596 KB Correct: 2179 out of 25000 queries used.
44 Correct 15 ms 524 KB Correct: 7950 out of 25000 queries used.
45 Correct 15 ms 500 KB Correct: 7909 out of 25000 queries used.
46 Correct 15 ms 516 KB Correct: 7861 out of 25000 queries used.
47 Correct 16 ms 528 KB Correct: 8055 out of 25000 queries used.
48 Correct 16 ms 516 KB Correct: 7996 out of 25000 queries used.
49 Correct 15 ms 524 KB Correct: 7907 out of 25000 queries used.
50 Correct 15 ms 468 KB Correct: 7921 out of 25000 queries used.
51 Correct 16 ms 468 KB Correct: 7917 out of 25000 queries used.
52 Correct 16 ms 516 KB Correct: 7980 out of 25000 queries used.
53 Correct 16 ms 524 KB Correct: 8000 out of 25000 queries used.
54 Correct 16 ms 468 KB Correct: 2821 out of 25000 queries used.
55 Correct 16 ms 464 KB Correct: 8102 out of 25000 queries used.
56 Correct 16 ms 472 KB Correct: 7997 out of 25000 queries used.
57 Correct 16 ms 524 KB Correct: 7964 out of 25000 queries used.
58 Correct 16 ms 512 KB Correct: 7963 out of 25000 queries used.
59 Correct 15 ms 468 KB Correct: 7935 out of 25000 queries used.
60 Correct 17 ms 464 KB Correct: 4053 out of 25000 queries used.
61 Correct 18 ms 516 KB Correct: 4607 out of 25000 queries used.
62 Correct 17 ms 468 KB Correct: 3814 out of 25000 queries used.
63 Correct 18 ms 516 KB Correct: 4603 out of 25000 queries used.
64 Correct 18 ms 468 KB Correct: 4181 out of 25000 queries used.
65 Correct 16 ms 540 KB Correct: 2191 out of 25000 queries used.
66 Correct 17 ms 532 KB Correct: 4423 out of 25000 queries used.
67 Correct 15 ms 596 KB Correct: 2062 out of 25000 queries used.
68 Correct 16 ms 548 KB Correct: 3000 out of 25000 queries used.
69 Correct 17 ms 544 KB Correct: 2910 out of 25000 queries used.
70 Correct 16 ms 544 KB Correct: 2841 out of 25000 queries used.