Submission #566710

#	Time	Username	Problem	Language	Result	Execution time	Memory
566710		SSRS	Factories (JOI14_factories)	C++14	100 / 100	3092 ms	115148 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const long long INF = 1000000000000000;
struct heavy_light_decomposition{
  vector<int> p, sz, in, next;
  vector<long long> d;
  heavy_light_decomposition(){
  }
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, vector<long long> &d): p(p), d(d){
    int N = p.size();
    sz = vector<int>(N, 1);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N, 0);
    int t = 0;
    dfs2(c, t);
  }
  void dfs1(vector<vector<int>> &c, int v = 0){
    for (int &w : c[v]){
      dfs1(c, w);
      sz[v] += sz[w];
      if (sz[w] > sz[c[v][0]]){
        swap(w, c[v][0]);
      }
    }
  }
  void dfs2(vector<vector<int>> &c, int &t, int v = 0){
    in[v] = t;
    t++;
    for (int w : c[v]){
      if (w == c[v][0]){
        next[w] = next[v];
      } else {
        next[w] = w;
      }
      dfs2(c, t, w);
    }
  }
  int lca(int u, int v){
    while (true){
      if (in[u] > in[v]){
        swap(u, v);
      }
      if (next[u] == next[v]){
        return u;
      }
      v = p[next[v]];
    }
  }
  long long dist(int u, int v){
    return d[u] + d[v] - 2 * d[lca(u, v)];
  }
};
heavy_light_decomposition HLD;
vector<vector<pair<long long, int>>> E2;
vector<long long> d2;
void Init(int N, int A[], int B[], int D[]){
  vector<vector<pair<int, int>>> E(N);
  for (int i = 0; i < N - 1; i++){
    E[A[i]].push_back(make_pair(D[i], B[i]));
    E[B[i]].push_back(make_pair(D[i], A[i]));
  }
  vector<int> p(N, -1);
  vector<vector<int>> c(N);
  vector<long long> d(N, 0);
  queue<int> Q;
  Q.push(0);
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    for (auto P : E[v]){
      int w = P.second;
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        d[w] = d[v] + P.first;
        Q.push(w);
      }
    }
  }
  HLD = heavy_light_decomposition(p, c, d);
  E2.resize(N);
  d2 = vector<long long>(N, -1);
}
long long Query(int S, int X[], int T, int Y[]){
  vector<pair<int, int>> V;
  for (int i = 0; i < S; i++){
    V.push_back(make_pair(HLD.in[X[i]], X[i]));
  }
  for (int i = 0; i < T; i++){
    V.push_back(make_pair(HLD.in[Y[i]], Y[i]));
  }
  sort(V.begin(), V.end());
  stack<int> st;
  st.push(V[0].second);
  for (int i = 1; i < S + T; i++){
    int v = HLD.lca(V[i - 1].second, V[i].second);
    while (!st.empty()){
      int w = st.top();
      if (HLD.d[v] < HLD.d[w]){
        st.pop();
        int pr = v;
        if (!st.empty()){
          if (HLD.d[pr] < HLD.d[st.top()]){
            pr = st.top();
          }
        }
        if (pr != w){
          long long D = HLD.d[w] - HLD.d[pr];
          E2[pr].push_back(make_pair(D, w));
          E2[w].push_back(make_pair(D, pr));
        }
      } else {
        break;
      }
    }
    if (st.empty()){
      st.push(v);
    } else if (st.top() != v){
      st.push(v);
    }
    if (st.top() != V[i].second){
      st.push(V[i].second);
    }
  }
  while (st.size() >= 2){
    int v = st.top();
    st.pop();
    int w = st.top();
    long long D = HLD.d[v] - HLD.d[w];
    E2[v].push_back(make_pair(D, w));
    E2[w].push_back(make_pair(D, v));
  }
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  for (int i = 0; i < S; i++){
    pq.push(make_pair(0, X[i]));
  }
  vector<int> s;
  while (!pq.empty()){
    long long c = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    if (d2[v] == -1){
      d2[v] = c;
      s.push_back(v);
      for (auto P : E2[v]){
        int w = P.second;
        if (d2[w] == -1){
          pq.push(make_pair(c + P.first, w));
        }
      }
    }
  }
  long long ans = INF;
  for (int i = 0; i < T; i++){
    ans = min(ans, d2[Y[i]]);
  }
  int cnt = s.size();
  for (int i = 0; i < cnt; i++){
    E2[s[i]].clear();
    d2[s[i]] = -1;
  }
  return ans;
}

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