oj.uz

Submission #851232

# Submission time Handle Problem Language Result Execution time Memory
851232 2023-09-19T03:59:56 Z NeroZein Factories (JOI14_factories) C++17
100 / 100
 4315 ms 178524 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std; 

const int LOG = 23;
const int MAX_N = 5e5 + 5; 

int cnt; 
int tp[MAX_N];
int dep[MAX_N];
int jump[LOG][MAX_N];
long long rdis[MAX_N]; 
bool important[MAX_N];
long long dp[MAX_N][3];
int in[MAX_N], out[MAX_N]; 
vector<pair<int, int>> g[MAX_N]; 
vector<pair<int, long long>> vg[MAX_N];

void dfs(int v, int p) {
  in[v] = cnt++;
  for (auto [u, w] : g[v]) {
    if (u == p) {
      continue;
    }
    dep[u] = dep[v] + 1;
    rdis[u] = rdis[v] + w;
    jump[0][u] = v;
    for (int i = 1; i < LOG; ++i) {
      jump[i][u] = jump[i - 1][jump[i - 1][u]];
    }
    dfs(u, v); 
  }
  out[v] = cnt - 1;
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int i = 0; i < LOG; ++i) {
    if ((dep[u] - dep[v]) >> i & 1) {
      u = jump[i][u];
    }
  }
  if (u == v) {
    return v;
  }
  for (int i = LOG - 1; i >= 0; --i) {
    if (jump[i][u] != jump[i][v]) {
      u = jump[i][u], v = jump[i][v];
    }
  }
  return jump[0][u];
}

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

long long dis(int u, int v) {
  return rdis[u] + rdis[v] - 2 * rdis[lca(u, v)];
}

long long dfs2(int v) {
  dp[v][1] = dp[v][2] =  1e15; 
  if (important[v]) {
    dp[v][tp[v]] = 0;
  }
  long long ret = LLONG_MAX; 
  for (auto [u, w] : vg[v]) {
    ret = min(ret, dfs2(u));
    dp[v][1] = min(dp[v][1], dp[u][1] + w); 
    dp[v][2] = min(dp[v][2], dp[u][2] + w); 
  }
  ret = min(ret, dp[v][1] + dp[v][2]);
  return ret;
}

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

long long Query(int S, int X[], int T, int Y[]) {
  vector<int> factories;
  for (int i = 0; i < S; ++i) {
    factories.push_back(X[i]);
    important[X[i]] = true;
    tp[X[i]] = 1;
  }
  bool rep = false;
  for (int i = 0; i < T; ++i) {
    factories.push_back(Y[i]); 
    important[Y[i]] = true;
    if (tp[Y[i]]) {
      rep = true;
    }
    tp[Y[i]] = 2;
  }
  sort(factories.begin(), factories.end(), [&](int u, int v) {
    return in[u] < in[v];
  });
  factories.push_back(0);
  for (int i = 0; i < S + T - 1; ++i) {
    factories.push_back(lca(factories[i], factories[i + 1]));
  }
  sort(factories.begin(), factories.end(), [&](int u, int v) {
    return in[u] < in[v];
  });
  factories.resize(unique(factories.begin(), factories.end()) - factories.begin());
  stack<int> stk; 
  assert(factories[0] == 0);
  stk.push(0);
  for (int i = 1; i < (int) factories.size(); ++i) {
    int cur = factories[i];
    while (!is_parent(cur, stk.top())) {
      stk.pop();
    }
    vg[stk.top()].emplace_back(cur, dis(cur, stk.top()));
    stk.push(cur);
  }
  long long ans = 0;
  if (!rep) {
    ans = dfs2(0);
  }
  for (int i = 0; i < S; ++i) {
    tp[X[i]] = 0;
    important[X[i]] = false;
  }
  for (int i = 0; i < T; ++i) {
    tp[Y[i]] = 0; 
    important[Y[i]] = false;
  }
  for (int i = 0; i < (int) factories.size(); ++i) {
    vg[factories[i]].clear(); 
  }
  return ans; 
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 93016 KB Output is correct
2 Correct 717 ms 97436 KB Output is correct
3 Correct 798 ms 97636 KB Output is correct
4 Correct 754 ms 97600 KB Output is correct
5 Correct 611 ms 98128 KB Output is correct
6 Correct 455 ms 97360 KB Output is correct
7 Correct 782 ms 97424 KB Output is correct
8 Correct 735 ms 97684 KB Output is correct
9 Correct 622 ms 97916 KB Output is correct
10 Correct 464 ms 97512 KB Output is correct
11 Correct 809 ms 97688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 93024 KB Output is correct
2 Correct 1666 ms 134956 KB Output is correct
3 Correct 2741 ms 141040 KB Output is correct
4 Correct 1071 ms 135536 KB Output is correct
5 Correct 2281 ms 178524 KB Output is correct
6 Correct 2935 ms 140808 KB Output is correct
7 Correct 1612 ms 106692 KB Output is correct
8 Correct 689 ms 105692 KB Output is correct
9 Correct 1297 ms 112476 KB Output is correct
10 Correct 1651 ms 107208 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 93016 KB Output is correct
2 Correct 717 ms 97436 KB Output is correct
3 Correct 798 ms 97636 KB Output is correct
4 Correct 754 ms 97600 KB Output is correct
5 Correct 611 ms 98128 KB Output is correct
6 Correct 455 ms 97360 KB Output is correct
7 Correct 782 ms 97424 KB Output is correct
8 Correct 735 ms 97684 KB Output is correct
9 Correct 622 ms 97916 KB Output is correct
10 Correct 464 ms 97512 KB Output is correct
11 Correct 809 ms 97688 KB Output is correct
12 Correct 14 ms 93024 KB Output is correct
13 Correct 1666 ms 134956 KB Output is correct
14 Correct 2741 ms 141040 KB Output is correct
15 Correct 1071 ms 135536 KB Output is correct
16 Correct 2281 ms 178524 KB Output is correct
17 Correct 2935 ms 140808 KB Output is correct
18 Correct 1612 ms 106692 KB Output is correct
19 Correct 689 ms 105692 KB Output is correct
20 Correct 1297 ms 112476 KB Output is correct
21 Correct 1651 ms 107208 KB Output is correct
22 Correct 2778 ms 143380 KB Output is correct
23 Correct 2716 ms 142768 KB Output is correct
24 Correct 2973 ms 148700 KB Output is correct
25 Correct 3416 ms 150136 KB Output is correct
26 Correct 3710 ms 141708 KB Output is correct
27 Correct 2792 ms 174808 KB Output is correct
28 Correct 1661 ms 140368 KB Output is correct
29 Correct 4006 ms 140832 KB Output is correct
30 Correct 4069 ms 139536 KB Output is correct
31 Correct 4315 ms 140364 KB Output is correct
32 Correct 1153 ms 114288 KB Output is correct
33 Correct 881 ms 108076 KB Output is correct
34 Correct 1258 ms 107080 KB Output is correct
35 Correct 1245 ms 106556 KB Output is correct
36 Correct 1455 ms 107192 KB Output is correct
37 Correct 1536 ms 107080 KB Output is correct