oj.uz

Submission #780071

# Submission time Handle Problem Language Result Execution time Memory
780071 2023-07-12T06:28:28 Z xink Factories (JOI14_factories) C++14
100 / 100
 4626 ms 489808 KB 
#include "factories.h"
#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <climits>
#include <cstring>
#include <algorithm>
#include <stack>
#include <functional>
#define ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
const int log_height = 20;
typedef vector<ll> vi;
typedef pair<ll, int> ii;
typedef vector<ii> vii;

vector<vii> adj_list, up;
vi tin, tout, dist, depth;
vii euler_tour;
int graph_sz, n_q = 0;
vi color;

int lg(unsigned long long i)
{
  return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

void get_euler_tour(int node, int par)
{
  tin[node] = euler_tour.size();
  euler_tour.push_back({depth[node], node});
  for (ii edge : adj_list[node])
  {
    if (edge.second == par)
      continue;
    depth[edge.second] = depth[node] + 1;
    dist[edge.second] = dist[node] + edge.first;
    get_euler_tour(edge.second, node);
    euler_tour.push_back({depth[node], node});
  }
  tout[node] = euler_tour.size() - 1;
}

void Init(int n, int u[], int v[], int w[])
{
  adj_list.assign(n, vii());
  graph_sz = n;
  for (int i = 0; i < n - 1; i++)
  {
    adj_list[u[i]].push_back({w[i], v[i]});
    adj_list[v[i]].push_back({w[i], u[i]});
  }
  tin.assign(n, -1);
  tout.assign(n, -1);
  depth.assign(n, 0);
  dist.assign(n, 0);
  color.assign(n, 0);
  get_euler_tour(0, -1);
  up.assign(euler_tour.size(), vii(log_height));
  for (int i = 0; i < euler_tour.size(); i++)
  {
    up[i][0] = euler_tour[i];
  }
  for (int i = 1; i < log_height; i++)
  {
    for (int j = 0; j < euler_tour.size(); j++)
    {
      up[j][i] = up[j][i - 1];
      if (j + (1 << (i - 1)) < euler_tour.size())
      {
        up[j][i] = min(up[j][i], up[j + (1 << (i - 1))][i - 1]);
      }
    }
  }
}

ii rmq(int l, int r)
{
  int lvl = lg(r - l + 1);
  return min(up[l][lvl], up[r - (1 << lvl) + 1][lvl]);
}

int get_lca(int u, int v)
{
  if (tin[u] > tin[v])
    swap(u, v);
  ii rmq_node = rmq(tin[u], tin[v]);
  return rmq_node.second;
}

bool comp(int u, int v)
{
  return tin[u] < tin[v];
}

ll Query(int s, int x[], int t, int y[])
{
  vi node;
  for (int i = 0; i < s; i++)
  {
    node.push_back(x[i]);
    color[x[i]] = 3 * n_q + 1;
  }
  for (int i = 0; i < t; i++)
  {
    node.push_back(y[i]);
    color[y[i]] = 3 * n_q + 2;
  }
  sort(node.begin(), node.end(), comp);
  for (int i = 1; i < s + t; i++)
  {
    int adj_lca = get_lca(node[i], node[i - 1]);
    if (color[adj_lca] <= 3 * n_q)
    {
      node.push_back(adj_lca);
      color[adj_lca] = 3 * n_q + 3;
    }
  }
  sort(node.begin(), node.end(), comp);
  int n = node.size();
  vector<vii> adj_list1(n);
  stack<ii> st;
  for (int i = 0; i < n; i++)
  {
    int id = node[i];
    while (!st.empty() && get_lca(st.top().first, id) != st.top().first)
    {
      st.pop();
    }
    if (!st.empty())
    {
      adj_list1[st.top().second].push_back({dist[id] - dist[st.top().first], i});
    }
    st.push({id, i});
  }
  vector<vi> dp(n, vi(3, LLONG_MAX / 2));
  std::function<void(int)> dfs = [&](int u)
  {
    dp[u][color[node[u]] % 3] = 0;
    for (ii edge : adj_list1[u])
    {
      dfs(edge.second);
      for (int i = 0; i < 3; i++)
      {
        dp[u][i] = min(dp[u][i], dp[edge.second][i] + edge.first);
      }
    }
  };
  dfs(0);
  ll min_dist = LLONG_MAX;
  for (int i = 0; i < n; i++)
  {
    min_dist = min(min_dist, dp[i][1] + dp[i][2]);
  }
  n_q++;
  return min_dist;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int i = 0; i < euler_tour.size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int j = 0; j < euler_tour.size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:72:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |       if (j + (1 << (i - 1)) < euler_tour.size())
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 980 KB Output is correct
2 Correct 846 ms 13060 KB Output is correct
3 Correct 957 ms 12712 KB Output is correct
4 Correct 860 ms 13168 KB Output is correct
5 Correct 698 ms 13388 KB Output is correct
6 Correct 589 ms 12856 KB Output is correct
7 Correct 914 ms 12648 KB Output is correct
8 Correct 865 ms 13152 KB Output is correct
9 Correct 702 ms 13388 KB Output is correct
10 Correct 598 ms 12836 KB Output is correct
11 Correct 936 ms 12800 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 1977 ms 438084 KB Output is correct
3 Correct 1873 ms 443788 KB Output is correct
4 Correct 1402 ms 435784 KB Output is correct
5 Correct 1590 ms 485792 KB Output is correct
6 Correct 2172 ms 444784 KB Output is correct
7 Correct 2031 ms 98116 KB Output is correct
8 Correct 928 ms 97332 KB Output is correct
9 Correct 845 ms 103912 KB Output is correct
10 Correct 1857 ms 99376 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 980 KB Output is correct
2 Correct 846 ms 13060 KB Output is correct
3 Correct 957 ms 12712 KB Output is correct
4 Correct 860 ms 13168 KB Output is correct
5 Correct 698 ms 13388 KB Output is correct
6 Correct 589 ms 12856 KB Output is correct
7 Correct 914 ms 12648 KB Output is correct
8 Correct 865 ms 13152 KB Output is correct
9 Correct 702 ms 13388 KB Output is correct
10 Correct 598 ms 12836 KB Output is correct
11 Correct 936 ms 12800 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 1977 ms 438084 KB Output is correct
14 Correct 1873 ms 443788 KB Output is correct
15 Correct 1402 ms 435784 KB Output is correct
16 Correct 1590 ms 485792 KB Output is correct
17 Correct 2172 ms 444784 KB Output is correct
18 Correct 2031 ms 98116 KB Output is correct
19 Correct 928 ms 97332 KB Output is correct
20 Correct 845 ms 103912 KB Output is correct
21 Correct 1857 ms 99376 KB Output is correct
22 Correct 3144 ms 452168 KB Output is correct
23 Correct 3073 ms 456284 KB Output is correct
24 Correct 3865 ms 457748 KB Output is correct
25 Correct 3761 ms 463100 KB Output is correct
26 Correct 4377 ms 445772 KB Output is correct
27 Correct 3285 ms 489808 KB Output is correct
28 Correct 2502 ms 451876 KB Output is correct
29 Correct 4429 ms 444896 KB Output is correct
30 Correct 4626 ms 444060 KB Output is correct
31 Correct 4211 ms 444976 KB Output is correct
32 Correct 1541 ms 114624 KB Output is correct
33 Correct 1252 ms 106420 KB Output is correct
34 Correct 1818 ms 96576 KB Output is correct
35 Correct 1659 ms 96600 KB Output is correct
36 Correct 1950 ms 97616 KB Output is correct
37 Correct 1945 ms 97524 KB Output is correct