Submission #258616

#	Time	Username	Problem	Language	Result	Execution time	Memory
258616		fedoseevtimofey	Factories (JOI14_factories)	C++14	100 / 100	6789 ms	140724 KiB

factories

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

#include "factories.h"

const int N = 5e5 + 7;
const int K = 20;
vector <pair <int, int>> g[N];
int go[K][N];
ll h[N];
int tin[N], tout[N];
int id[N];

int timer = 0;

int n;

void dfs(int u, int p) {
  tin[u] = timer++;
  go[0][u] = p;
  for (int i = 1; i < K; ++i) {
    go[i][u] = go[i - 1][go[i - 1][u]];
  }
  for (auto pr : g[u]) {
    int v = pr.first, w = pr.second;
    if (v != p) {
      h[v] = h[u] + w;
      dfs(v, u);
    }
  } 
  tout[u] = timer++;
}

bool anc(int a, int b) {
  return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca(int a, int b) {
  if (anc(a, b)) return a;
  for (int i = K - 1; i >= 0; --i) {
    if (!anc(go[i][a], b)) {
      a = go[i][a];
    }
  }
  return go[0][a];
}

ll dist(int a, int b) {
  return h[a] + h[b] - 2 * h[lca(a, b)];
}
  
void Init(int N, int A[], int B[], int D[]) {
  n = N;
  for (int i = 0; i + 1 < n; ++i) {
    g[A[i]].push_back({B[i], D[i]});
    g[B[i]].push_back({A[i], D[i]});
  }
  dfs(0, 0);
} 

long long Query(int s, int X[], int t, int Y[]) {
  vector <int> vr;
  for (int i = 0; i < s; ++i) vr.push_back(X[i]);
  for (int i = 0; i < t; ++i) vr.push_back(Y[i]);
  sort(vr.begin(), vr.end(), [&] (int a, int b) {
    return tin[a] < tin[b];
  });
  {
    vector <int> nvr;
    for (int i = 0; i < (int)vr.size(); ++i) {
      int j = (i + 1) % (int)vr.size();
      nvr.push_back(lca(vr[i], vr[j]));
    }
    for (int x : vr) nvr.push_back(x);
    vr = nvr;
    sort(vr.begin(), vr.end());
    vr.resize(unique(vr.begin(), vr.end()) - vr.begin());
    sort(vr.begin(), vr.end(), [&] (int a, int b) {
      return tin[a] < tin[b];
    });
  }
  int k = vr.size();
  for (int i = 0; i < k; ++i) id[vr[i]] = i;
  vector <vector <pair <int, ll>>> ng(k);
  vector <int> st;
  for (int i = 0; i < k; ++i) {
    while (!st.empty() && !anc(st.back(), vr[i])) {
      st.pop_back();
    }
    if (!st.empty()) {
      ng[id[st.back()]].push_back({id[vr[i]], dist(st.back(), vr[i])});
      ng[id[vr[i]]].push_back({id[st.back()], dist(st.back(), vr[i])});
    }
    st.push_back(vr[i]);
  }
  vector <int> tp(k, -1);
  for (int i = 0; i < s; ++i) {
    tp[id[X[i]]] = 0;
  }
  for (int i = 0; i < t; ++i) {
    tp[id[Y[i]]] = 1;
  }
  const ll Inf = 1e18;
  vector <ll> dp(k, Inf);
  vector <ll> sdp(k, Inf);
  function <void(int, int)> jhfs = [&] (int u, int p) {
    if (tp[u] == 0) dp[u] = 0;
    for (auto pr : ng[u]) {
      int v = pr.first; ll w = pr.second;
      if (v != p) {
        jhfs(v, u);
        ll x = dp[v] + w;
        if (x < dp[u]) {
          swap(x, dp[u]);
        }
        if (x < sdp[u]) {
          swap(x, sdp[u]);
        }
      }
    }
  };    
  jhfs(0, 0);
  vector <ll> dpU(k, Inf);

  function <void(int, int, ll)> zhfs = [&] (int u, int p, ll best) {
    if (tp[u] == 0) best = 0;
    dpU[u] = best;
    for (auto pr : ng[u]) {
      int v = pr.first; ll w = pr.second;
      if (v != p) {
        ll go = best + w;
        if (dp[v] + w != dp[u]) {
          go = min(go, dp[u] + w);
        } else {
          go = min(go, sdp[u] + w);
        }
        zhfs(v, u, go);
      }
    }
  };    
  zhfs(0, 0, Inf);
  ll ans = Inf;
  for (int i = 0; i < k; ++i) {
    if (tp[i] == 1) {
      ans = min(ans, dp[i]);
      ans = min(ans, dpU[i]);
    }
  }
  return ans;
}

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