oj.uz

Submission #361950

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

  ll result = inf;
  for(int i = 0; i < fact2.size(); i++)
    result = std::min(result, dist1[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 'll solve(std::vector<int>, std::vector<int>, std::vector<int>)':
factories.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i = 0; i < base.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
factories.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int i = 0; i < fact1.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
factories.cpp:107: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]
  107 |       for(int h = 0; h < secg[node].size(); h++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(int i = 0; i < fact2.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for(int i = 1; i < base.size(); i++)
      |                  ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 24684 KB Output is correct
2 Correct 2029 ms 42952 KB Output is correct
3 Correct 2233 ms 43064 KB Output is correct
4 Correct 2107 ms 43136 KB Output is correct
5 Correct 1764 ms 43060 KB Output is correct
6 Correct 1385 ms 42860 KB Output is correct
7 Correct 2212 ms 42704 KB Output is correct
8 Correct 2070 ms 42984 KB Output is correct
9 Correct 1734 ms 43368 KB Output is correct
10 Correct 1476 ms 42952 KB Output is correct
11 Correct 2249 ms 42540 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24300 KB Output is correct
2 Correct 3448 ms 140896 KB Output is correct
3 Correct 6043 ms 143936 KB Output is correct
4 Correct 1994 ms 141012 KB Output is correct
5 Correct 3659 ms 178084 KB Output is correct
6 Correct 6385 ms 146208 KB Output is correct
7 Correct 6864 ms 67112 KB Output is correct
8 Correct 2389 ms 67072 KB Output is correct
9 Correct 3752 ms 72472 KB Output is correct
10 Correct 6299 ms 68852 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 24684 KB Output is correct
2 Correct 2029 ms 42952 KB Output is correct
3 Correct 2233 ms 43064 KB Output is correct
4 Correct 2107 ms 43136 KB Output is correct
5 Correct 1764 ms 43060 KB Output is correct
6 Correct 1385 ms 42860 KB Output is correct
7 Correct 2212 ms 42704 KB Output is correct
8 Correct 2070 ms 42984 KB Output is correct
9 Correct 1734 ms 43368 KB Output is correct
10 Correct 1476 ms 42952 KB Output is correct
11 Correct 2249 ms 42540 KB Output is correct
12 Correct 20 ms 24300 KB Output is correct
13 Correct 3448 ms 140896 KB Output is correct
14 Correct 6043 ms 143936 KB Output is correct
15 Correct 1994 ms 141012 KB Output is correct
16 Correct 3659 ms 178084 KB Output is correct
17 Correct 6385 ms 146208 KB Output is correct
18 Correct 6864 ms 67112 KB Output is correct
19 Correct 2389 ms 67072 KB Output is correct
20 Correct 3752 ms 72472 KB Output is correct
21 Correct 6299 ms 68852 KB Output is correct
22 Correct 7892 ms 150456 KB Output is correct
23 Correct 6999 ms 141072 KB Output is correct
24 Execution timed out 8019 ms 146872 KB Time limit exceeded
25 Halted 0 ms 0 KB -