Submission #1152955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152955		tht2005	Factories (JOI14_factories)	C++17	100 / 100	2073 ms	150492 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;
typedef long long ll;

const int N = (int)5e5 + 10;
const int L = 19;

int type[N];
ll res, f[N][2];
vector< pair<ll, int> > virt_aj[N];
void dfs2(int v) {
  f[v][0] = f[v][1] = 1LL<<60;
  if(type[v] != -1) {
    f[v][type[v]] = 0;
  }
  for(const pair<ll, int>& tmp : virt_aj[v]) {
    ll w = tmp.first;
    int u = tmp.second;
    dfs2(u);
    res = min(res,
                min(f[u][0] + w + f[v][1], f[u][1] + w + f[v][0]));
    for(int t = 2; t--; ) {
      f[v][t] = min(f[v][t], f[u][t] + w);
    }
  }
}

int timer=0, tin[N], tout[N], par[N][L];
ll sum[N];
vector<pi> aj[N];

void dfs(int v, int p=-1) {
  tin[v] = timer++;
  memset(par[v], -1, sizeof(par[v]));
  par[v][0] = p;
  for(int i = 0; i + 1 < L && par[v][i] != -1; ++i) {
    par[v][i + 1] = par[par[v][i]][i];
  }
  for(const pi& x : aj[v]) {
    int u = x.second;
    if(u == p) {
      continue;
    }
    sum[u] = sum[v] + x.first;
    dfs(u, v);
  }
  tout[v] = timer;
}

bool anc(int p, int c) {
  return tin[p] <= tin[c] && tin[c] < tout[p];
}
int lca(int u, int v) {
  if(anc(u, v)) return u;
  if(anc(v, u)) return v;
  for(int i = L; i--; ) {
    if(par[v][i] != -1 && !anc(par[v][i], u)) {
      v = par[v][i];
    }
  }
  return par[v][0];
}

void Init(int N, int A[], int B[], int D[]) {
  for(int i = 0; i < N - 1; ++i) {
    aj[A[i]].emplace_back(D[i], B[i]);
    aj[B[i]].emplace_back(D[i], A[i]);
  }
  dfs(0);
}

long long Query(int S, int X[], int T, int Y[]) {
  vector<pi> ord;
  for(int i = 0; i < S; ++i)
    ord.emplace_back(tin[X[i]], X[i]);
  for(int i = 0; i < T; ++i)
    ord.emplace_back(tin[Y[i]], Y[i]);
  sort(ord.begin(), ord.end());
  for(int i = 0, sz = ord.size(); i + 1 < sz; ++i) {
    int x = lca(ord[i].second, ord[i + 1].second);
    ord.emplace_back(tin[x], x);
  }
  sort(ord.begin(), ord.end());
  ord.erase(unique(ord.begin(), ord.end()), ord.end());
  for(const pi& tmp : ord) {
    virt_aj[tmp.second].clear();
    type[tmp.second] = -1;
  }
  for(int i = 0; i < S; ++i) {
    type[X[i]] = 0;
  }
  for(int i = 0; i < T; ++i) {
    type[Y[i]] = 1;
  }
  stack<int> stk;
  for(const pi& tmp : ord) {
    int c = tmp.second;
    while(!stk.empty() && !anc(stk.top(), c)) {
      stk.pop();
    }
    if(!stk.empty()) {
      int r = stk.top();
      virt_aj[r].emplace_back(sum[c] - sum[r], c);
    }
    stk.push(c);
  }
  int root = ord.front().second;
  res = 1LL<<60;
  dfs2(root);
  return res;
}

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