Submission #881765

#	Time	Username	Problem	Language	Result	Execution time	Memory
881765		Tob	Factories (JOI14_factories)	C++14	100 / 100	4207 ms	195876 KiB

factories

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 5e5 + 7;
const ll inf = 1e18;

int n, tim;
int par[N][21], dub[N], st[N], en[N];
ll ps[N], dow[N], up[N];
bool good[N];
vector <pii> adj[N], gadj[N];

int lca(int x, int y) {
  if (dub[x] < dub[y]) swap(x, y);
  for (int i = 20; i >= 0; i--) {
    int z = par[x][i];
    if (dub[z] >= dub[y]) x = z;
  }
  if (x == y) return x;
  for (int i = 20; i >= 0; i--) {
    int z = par[x][i], w = par[y][i];
    if (z != w) x = z, y = w;
  }
  return par[x][0];
}

void dfs(int x = 1, int p = 0) {
  dub[x] = dub[p]+1;
  par[x][0] = p;
  st[x] = ++tim;
  for (auto it : adj[x]) {
    if (it.F == p) continue;
    ps[it.F] = ps[x] + it.S;
    dfs(it.F, x);
  }
  en[x] = tim;
}

void DP(int x, bool rev) {
  if (!rev) {
    dow[x] = inf;
    if (good[x]) dow[x] = 0;
    for (auto y : gadj[x]) {
      DP(y.F, 0);
      dow[x] = min(dow[x], dow[y.F] + y.S);
    }
  }
  else {
    if (good[x]) up[x] = 0;
    int siz = gadj[x].size();
    vector <ll> pr(siz+2, inf), su(siz+2, inf);
    for (int i = 0; i < siz; i++) {
      pii y = gadj[x][i];
      pr[i+1] = min(pr[i], dow[y.F] + y.S);
    }
    for (int i = siz-1; i >= 0; i--) {
      pii y = gadj[x][i];
      su[i+1] = min(su[i+2], dow[y.F] + y.S);
    }
    for (int i = 0; i < siz; i++) {
      pii y = gadj[x][i];
      up[y.F] = min(up[x], min(pr[i], su[i+2])) + y.S;
      DP(y.F, 1);
    }
  }
}

void Init(int nn, int A[], int B[], int D[]) {
  n = nn;
  for (int i = 0; i < n-1; i++) {
    A[i]++; B[i]++;
    adj[A[i]].pb({B[i], D[i]});
    adj[B[i]].pb({A[i], D[i]});
  }
  dfs();
  for (int k = 1; k <= 20; k++) {
    for (int i = 1; i <= n; i++) {
      par[i][k] = par[par[i][k-1]][k-1];
    }
  }
}

bool cmp(int x, int y) {
  return st[x] < st[y];
}

ll Query(int S, int X[], int T, int Y[]) {
  up[1] = inf;
  vector <int> v;
  for (int i = 0; i < S; i++) v.pb(++X[i]);
  for (int i = 0; i < T; i++) v.pb(++Y[i]);
  sort(all(v), cmp);
  for (int i = 1; i < S+T; i++) v.pb(lca(v[i-1], v[i]));
  v.pb(1);
  sort(all(v), cmp);
  vector <int> v2;
  v2.pb(1);
  for (int i = 1; i < v.size(); i++) if (v[i-1] != v[i]) {
    int x = v[i];
    while (en[v2.back()] < st[x]) v2.pop_back();
    int y = v2.back();
    gadj[y].pb({x, ps[x]-ps[y]});
    v2.pb(x);
  }
  for (int i = 0; i < S; i++) good[X[i]] = 1;
  DP(1, 0);
  DP(1, 1);
  ll mn = inf;
  for (int i = 0; i < T; i++) mn = min(mn, min(dow[Y[i]], up[Y[i]]));
  for (auto x : v) {
    gadj[x].clear();
    up[x] = dow[x] = 0;
    good[x] = 0;
  }
  return mn;
}

Compilation message (stderr)

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for (int i = 1; i < v.size(); i++) if (v[i-1] != v[i]) {
      |                   ~~^~~~~~~~~~

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