Submission #361960

#	Time	Username	Problem	Language	Result	Execution time	Memory
361960		AlexLuchianov	Factories (JOI14_factories)	C++14	100 / 100	4647 ms	211668 KiB

factories

#include "factories.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>
#include <stack>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 500000;
int const lgmax = 20;
ll const inf = 1000000000000000000;

std::vector<std::pair<int,int>> g[1 + nmax];
int far[1 + lgmax][1 + nmax];
int id[1 + nmax], level[1 + nmax];
ll dist[1 + nmax];

int rmq[1 + lgmax][1 + nmax * 2];
int pos_glob[1 + nmax * 2], glob = 0;

void dfs(int node, int parent, int &acc) {
  id[node] = ++acc;
  pos_glob[node] = glob++;
  rmq[0][glob - 1] = node;

  for(int h = 0; h < g[node].size(); h++) {
    std::pair<int,int> edge = g[node][h];
    if(edge.first != parent) {
      level[edge.first] = level[node] + 1;
      far[0][edge.first] = node;
      dist[edge.first] = dist[node] + edge.second;
      dfs(edge.first, node, acc);
      rmq[0][glob++] = node;
    }
  }
}

int getbest(int x, int y) {
  if(level[x] < level[y])
    return x;
  else
    return y;
}

int lg(int x) {
  return 31 - __builtin_clz(x);
}

int lca(int x, int y) {
  x = pos_glob[x];
  y = pos_glob[y];
  if(y < x)
    std::swap(x, y);
  int h = lg(y - x + 1);
  return getbest(rmq[h][x], rmq[h][y - (1 << h) + 1]);
}

int isanc(int x, int y) {
  return lca(x, y) == x;
}

ll getdist(int x, int y) {
  return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}

void Init(int N, int A[], int B[], int D[]) {
  for(int i = 0; i < N - 1; i++) {
    g[A[i]].push_back({B[i], D[i]});
    g[B[i]].push_back({A[i], D[i]});
  }
  int acc = 0;
  dfs(0, -1, acc);
  for(int h = 1; h <= lgmax; h++) 
    for(int i = 0; i < glob - (1 << h) + 1; i++)
      rmq[h][i] = getbest(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
}

bool compare(int x, int y) {
  return id[x] < id[y];
}

std::vector<std::pair<int,ll>> secg[1 + nmax];
ll dist1[1 + nmax];
ll dp[1 + nmax], dp2[1 + nmax];

void computedp(int node, int parent) {
  for(int h = 0; h < secg[node].size(); h++) {
    std::pair<int, ll> edge = secg[node][h];
    if(edge.first != parent) {
      computedp(edge.first, node);
      dp[node] = std::min(dp[node], dp[edge.first] + edge.second);
    }
  }
}

void computedp2(int node, int parent) {
  dp2[node] = std::min(dp2[node], dp[node]);
  for(int h = 0; h < secg[node].size(); h++) {
    std::pair<int, ll> edge = secg[node][h];
    if(edge.first != parent) {
      dp2[edge.first] = std::min(dp2[edge.first], dp2[node] + edge.second);
      computedp2(edge.first, node);
    }
  }
}

ll solve(std::vector<int> &base, std::vector<int> &fact1, std::vector<int> &fact2) {
  for(int i = 0; i < base.size(); i++) {
    secg[base[i]].clear();
    dist1[base[i]] = inf;
    dp[base[i]] = dp2[base[i]] = inf;
  }
  
  for(int i = 0; i < fact1.size(); i++)
    dp[fact1[i]] = 0;

  std::stack<int> st;
  for(int i = 0; i < base.size(); i++) {
    while(0 < st.size() && isanc(st.top(), base[i]) == 0)
      st.pop();
    if(0 < st.size()) {
      ll travel = getdist(st.top(), base[i]);
      secg[st.top()].push_back({base[i], travel});
      secg[base[i]].push_back({st.top(), travel});
    }
    st.push(base[i]);
  }
  computedp(base[0], -1);
  computedp2(base[0], -1);
  ll result = inf;
  for(int i = 0; i < fact2.size(); i++)
    result = std::min(result, dp2[fact2[i]]);
  return result;
}

long long Query(int S, int X[], int T, int Y[]) {
  std::vector<int> base;
  for(int i = 0; i < S; i++)
    base.push_back(X[i]);
  for(int i = 0; i < T; i++)
    base.push_back(Y[i]);
  
  std::sort(base.begin(), base.end(), compare);
  std::vector<int> aux = base;
  for(int i = 1; i < base.size(); i++)
    aux.push_back(lca(base[i - 1], base[i]));
  std::sort(aux.begin(), aux.end(), compare);
  aux.erase(std::unique(aux.begin(), aux.end()), aux.end());
  std::vector<int> fact1, fact2;
  for(int i = 0; i < S; i++)
    fact1.push_back(X[i]);
  for(int i = 0; i < T; i++)
    fact2.push_back(Y[i]);
  return solve(aux, fact1, fact2);
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int, int&)':
factories.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void computedp(int, int)':
factories.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int h = 0; h < secg[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void computedp2(int, int)':
factories.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int h = 0; h < secg[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'll solve(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
factories.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for(int i = 0; i < fact1.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:136:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for(int i = 0; i < fact2.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:150:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |   for(int i = 1; i < base.size(); i++)
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67