oj.uz

Submission #361956

# Submission time Handle Problem Language Result Execution time Memory
361956 2021-02-01T11:14:40 Z AlexLuchianov Factories (JOI14_factories) C++14
33 / 100
 8000 ms 167312 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];

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];
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: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 'void computedp(int, int)':
factories.cpp:80: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]
   80 |   for(int h = 0; h < secg[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void computedp2(int, int)':
factories.cpp:91: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]
   91 |   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:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int i = 0; i < fact1.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int i = 0; i < fact2.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i = 1; i < base.size(); i++)
      |                  ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 24428 KB Output is correct
2 Correct 1836 ms 33596 KB Output is correct
3 Correct 2052 ms 33280 KB Output is correct
4 Correct 1862 ms 33752 KB Output is correct
5 Correct 1588 ms 33644 KB Output is correct
6 Correct 1209 ms 33388 KB Output is correct
7 Correct 1978 ms 33592 KB Output is correct
8 Correct 1830 ms 33772 KB Output is correct
9 Correct 1596 ms 33900 KB Output is correct
10 Correct 1200 ms 33384 KB Output is correct
11 Correct 1997 ms 33656 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24172 KB Output is correct
2 Correct 3339 ms 130284 KB Output is correct
3 Correct 5905 ms 133896 KB Output is correct
4 Correct 1951 ms 130884 KB Output is correct
5 Correct 3563 ms 167312 KB Output is correct
6 Correct 6292 ms 135532 KB Output is correct
7 Correct 6665 ms 55228 KB Output is correct
8 Correct 2310 ms 54860 KB Output is correct
9 Correct 3802 ms 60164 KB Output is correct
10 Correct 6388 ms 56412 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 24428 KB Output is correct
2 Correct 1836 ms 33596 KB Output is correct
3 Correct 2052 ms 33280 KB Output is correct
4 Correct 1862 ms 33752 KB Output is correct
5 Correct 1588 ms 33644 KB Output is correct
6 Correct 1209 ms 33388 KB Output is correct
7 Correct 1978 ms 33592 KB Output is correct
8 Correct 1830 ms 33772 KB Output is correct
9 Correct 1596 ms 33900 KB Output is correct
10 Correct 1200 ms 33384 KB Output is correct
11 Correct 1997 ms 33656 KB Output is correct
12 Correct 22 ms 24172 KB Output is correct
13 Correct 3339 ms 130284 KB Output is correct
14 Correct 5905 ms 133896 KB Output is correct
15 Correct 1951 ms 130884 KB Output is correct
16 Correct 3563 ms 167312 KB Output is correct
17 Correct 6292 ms 135532 KB Output is correct
18 Correct 6665 ms 55228 KB Output is correct
19 Correct 2310 ms 54860 KB Output is correct
20 Correct 3802 ms 60164 KB Output is correct
21 Correct 6388 ms 56412 KB Output is correct
22 Correct 7328 ms 141244 KB Output is correct
23 Correct 6740 ms 141060 KB Output is correct
24 Correct 7767 ms 145340 KB Output is correct
25 Execution timed out 8029 ms 148164 KB Time limit exceeded
26 Halted 0 ms 0 KB -