Submission #1231400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231400		lmquan	Factories (JOI14_factories)	C++17	100 / 100	5997 ms	149832 KiB

factories

#include "factories.h"
#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kN = 500005;
const int kLG = 20;
const long long kInf = 91632847297843575;

vector<pair<int, int>> children[kN];
int in[kN], out[kN], jump[kLG][kN], timer;
bool markX[kN], markY[kN];
long long p[kN], dp[2][kN];
vector<pair<int, long long>> vt[kN];

void DFS(int u, int v) {
  in[u] = ++timer;
  jump[0][u] = v;
  for (int i = 1; i < kLG; i++) {
    jump[i][u] = jump[i - 1][jump[i - 1][u]];
  }
  for (auto i : children[u]) {
   if (i.first == v) {
     continue;
   }
   p[i.first] = p[u] + i.second;
   DFS(i.first, u);
  }
  out[u] = timer;
}

bool Ancestor(int u, int v) {
  return (in[v] <= in[u] && out[u] <= out[v]);
}

int LCA(int u, int v) {
  if (Ancestor(u, v)) {
   return v;
  }
  for (int i = kLG - 1; i >= 0; i--) {
   if (jump[i][v] != -1 && !Ancestor(u, jump[i][v])) {
     v = jump[i][v];
   }
  }
  return jump[0][v];
}

bool DFSTimer(int u, int v) {
  return in[u] < in[v];
}

long long SumPath(int x, int y) {
  return p[y] + p[x] - 2 * p[LCA(x, y)];
}

void Init(int N, int A[], int B[], int D[]) {
  memset(jump, -1, sizeof(jump));
  for (int i = 0; i < N - 1; i++) {
   children[A[i]].push_back(make_pair(B[i], D[i]));
   children[B[i]].push_back(make_pair(A[i], D[i]));
  }
  int root = 0;
  DFS(root, root);
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < 2; j++) {
     dp[j][i] = kInf;
   }
  }
}

long long Query(int S, int X[], int T, int Y[]) {
  vector<int> u;
  for (int i = 0; i < S; i++) {
   markX[X[i]] = true;
   u.push_back(X[i]);
  }
  for (int i = 0; i < T; i++) {
   markY[Y[i]] = true;
   u.push_back(Y[i]);
  }

  sort(u.begin(), u.end(), DFSTimer);
  int l = u.size() - 1;
  for (int i = 0; i < l; i++) {
   u.push_back(LCA(u[i], u[i + 1]));
  }
  sort(u.begin(), u.end(), DFSTimer);
  u.erase(unique(u.begin(), u.end()), u.end());
  stack<int> st;
  st.push(u[0]);
  for (int i = 1; i < u.size(); i++) {
    while (!st.empty() && !Ancestor(u[i], st.top())) {
      st.pop();
    }
    vt[st.top()].push_back(make_pair(u[i], SumPath(st.top(), u[i])));
    st.push(u[i]);
  }

  function<void(int i)> CalculateDP = [&](int i) {
   if (markX[i]) {
     dp[0][i] = 0;
   }
   if (markY[i]) {
     dp[1][i] = 0;
   }
   for (auto j : vt[i]) {
     CalculateDP(j.first);
     if (dp[0][j.first] != kInf) {
       dp[0][i] = min(dp[0][i], dp[0][j.first] + j.second);
     }
     if (dp[1][j.first] != kInf) {
       dp[1][i] = min(dp[1][i], dp[1][j.first] + j.second);
     }
   }
  };

  CalculateDP(u[0]);

  long long result = kInf;
  for (int i : u) {
   if (dp[0][i] != kInf && dp[1][i] != kInf) {
     result = min(result, dp[0][i] + dp[1][i]);
   }
  }

  for (int i : u) {
   dp[0][i] = dp[1][i] = kInf;
   vt[i].clear();
  }
  for (int i = 0; i < S; i++) {
   markX[X[i]] = false;
  }
  for (int i = 0; i < T; i++) {
   markY[Y[i]] = false;
  }

  return result;
}

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