Submission #361953

#	Time	Username	Problem	Language	Result	Execution time	Memory
361953		AlexLuchianov	Factories (JOI14_factories)	C++14	33 / 100	8090 ms	161452 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];

void dfs(int node, int parent, int &acc) {
  id[node] = ++acc;
  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);
    }
  }
}

int lca(int x, int y) {
  if(level[x] < level[y])
    std::swap(x, y);
  for(int h = lgmax; 0 <= h; h--)
    if(level[y] + (1 << h) <= level[x])
      x = far[h][x];
  if(x == y)
    return x;
  for(int h = lgmax; 0 <= h; h--)
    if(far[h][x] != far[h][y]) {
      x = far[h][x];
      y = far[h][y];
    }
  return far[0][x];
}
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 < N; i++)
      far[h][i] = far[h - 1][far[h - 1][i]]; 
}

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

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

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;
    isspec[base[i]] = 0;
  }
  for(int i = 0; i < fact2.size(); i++)
    isspec[fact2[i]] = 1;
  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]);
  }

  std::priority_queue<std::pair<ll,int>, std::vector<std::pair<ll,int>>, std::greater<std::pair<ll, int>>> pq;
  for(int i = 0; i < fact1.size(); i++) {
    dist1[fact1[i]] = 0;
    pq.push({0, fact1[i]});
  }

  while(0 < pq.size()) {
    std::pair<ll, int> pqtop = pq.top();
    pq.pop();
    
    if(pqtop.first == dist1[pqtop.second]) {
      int node = pqtop.second;
      if(isspec[node] == 1)
        return pqtop.first;

      for(int h = 0; h < secg[node].size(); h++) {
        std::pair<int, ll> edge = secg[node][h];
        if(dist1[node] + edge.second < dist1[edge.first]){
          dist1[edge.first] = dist1[node] + edge.second;
          pq.push({dist1[edge.first], edge.first});
        }
      }
    }
  }
  return inf;
}

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:25: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]
   25 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'll solve(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
factories.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i = 0; i < fact2.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i = 0; i < fact1.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
factories.cpp:114:24: 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]
  114 |       for(int h = 0; h < secg[node].size(); h++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for(int i = 1; i < base.size(); i++)
      |                  ~~^~~~~~~~~~~~~

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