Submission #780071

#	Time	Username	Problem	Language	Result	Execution time	Memory
780071		xink	Factories (JOI14_factories)	C++14	100 / 100	4626 ms	489808 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67