oj.uz

Submission #361960

# Submission time Handle Problem Language Result Execution time Memory
361960 2021-02-01T11:22:56 Z AlexLuchianov Factories (JOI14_factories) C++14
100 / 100
 4647 ms 211668 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24556 KB Output is correct
2 Correct 1210 ms 34028 KB Output is correct
3 Correct 1209 ms 34156 KB Output is correct
4 Correct 1243 ms 34156 KB Output is correct
5 Correct 1102 ms 34668 KB Output is correct
6 Correct 767 ms 34160 KB Output is correct
7 Correct 1166 ms 34284 KB Output is correct
8 Correct 1187 ms 34556 KB Output is correct
9 Correct 1090 ms 34412 KB Output is correct
10 Correct 776 ms 34168 KB Output is correct
11 Correct 1183 ms 34028 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24248 KB Output is correct
2 Correct 1836 ms 167276 KB Output is correct
3 Correct 2092 ms 171116 KB Output is correct
4 Correct 1377 ms 167764 KB Output is correct
5 Correct 1753 ms 204396 KB Output is correct
6 Correct 2236 ms 172444 KB Output is correct
7 Correct 2164 ms 61292 KB Output is correct
8 Correct 1220 ms 61092 KB Output is correct
9 Correct 1367 ms 66412 KB Output is correct
10 Correct 2088 ms 62444 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24556 KB Output is correct
2 Correct 1210 ms 34028 KB Output is correct
3 Correct 1209 ms 34156 KB Output is correct
4 Correct 1243 ms 34156 KB Output is correct
5 Correct 1102 ms 34668 KB Output is correct
6 Correct 767 ms 34160 KB Output is correct
7 Correct 1166 ms 34284 KB Output is correct
8 Correct 1187 ms 34556 KB Output is correct
9 Correct 1090 ms 34412 KB Output is correct
10 Correct 776 ms 34168 KB Output is correct
11 Correct 1183 ms 34028 KB Output is correct
12 Correct 20 ms 24248 KB Output is correct
13 Correct 1836 ms 167276 KB Output is correct
14 Correct 2092 ms 171116 KB Output is correct
15 Correct 1377 ms 167764 KB Output is correct
16 Correct 1753 ms 204396 KB Output is correct
17 Correct 2236 ms 172444 KB Output is correct
18 Correct 2164 ms 61292 KB Output is correct
19 Correct 1220 ms 61092 KB Output is correct
20 Correct 1367 ms 66412 KB Output is correct
21 Correct 2088 ms 62444 KB Output is correct
22 Correct 4529 ms 179428 KB Output is correct
23 Correct 3744 ms 179096 KB Output is correct
24 Correct 4647 ms 183200 KB Output is correct
25 Correct 4302 ms 185552 KB Output is correct
26 Correct 4274 ms 177700 KB Output is correct
27 Correct 3970 ms 211668 KB Output is correct
28 Correct 2551 ms 182916 KB Output is correct
29 Correct 4027 ms 181856 KB Output is correct
30 Correct 4054 ms 181184 KB Output is correct
31 Correct 3982 ms 181780 KB Output is correct
32 Correct 2133 ms 82968 KB Output is correct
33 Correct 1351 ms 78504 KB Output is correct
34 Correct 2553 ms 73164 KB Output is correct
35 Correct 2353 ms 72952 KB Output is correct
36 Correct 2572 ms 73708 KB Output is correct
37 Correct 2439 ms 73548 KB Output is correct