oj.uz

Submission #499059

# Submission time Handle Problem Language Result Execution time Memory
499059 2021-12-27T07:13:08 Z 600Mihnea Factories (JOI14_factories) C++17
15 / 100
 8000 ms 229476 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

typedef long long ll;
const int N = (int) 5e5 + 7;
const int K = 21;
int n;
int indexOfNode[N];
int currentIndex;
int secondCurrentIndex;
int dep[N];
int first[N];
int last[N];
int lg[2 * N];
vector<pair<int, int>> g[N];
pair<int, int> rmq[K][2 * N];
ll sum[N];

void addEdgeToGraph(int a, int b, int d) {
  g[a].push_back({b, d});
  g[b].push_back({a, d});
}

void build_stuff(int a, int p = 0) {
  indexOfNode[a] = ++currentIndex;
  rmq[0][++secondCurrentIndex] = {dep[a], a};
  first[a] = secondCurrentIndex;
  for (auto &it : g[a]) {
    int b = it.first;
    int cost = it.second;
    if (b != p) {
      dep[b] = 1 + dep[a];
      sum[b] = cost + sum[a];
      build_stuff(b, a);
      rmq[0][++secondCurrentIndex] = {dep[a], a};
    }
  }
  last[a] = secondCurrentIndex;
}

int getlca(int a, int b) {
  if (first[a] > last[b]) {
    swap(a, b);
  }
  a = first[a];
  b = last[b];
  assert(a <= b);
  int k = lg[b - a + 1];
  return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}

void Init(int nn, int edges_a[], int edges_b[], int edges_d[]) {
  n = nn;
  for (int i = 1; i <= n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    addEdgeToGraph(edges_a[i] + 1, edges_b[i] + 1, edges_d[i]);
  }
  build_stuff(1);
  for (int i = 2; i <= secondCurrentIndex; i++) {
    lg[i] = 1 + lg[i / 2];
  }
  for (int k = 1; (1 << k) <= secondCurrentIndex; k++) {
    for (int i = 1; i + (1 << k) - 1 <= secondCurrentIndex; i++) {
      rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
    }
  }
  /*for (int i = 1; i <= n; i++) {
    assert(getlca(i, i) == i);
    for (int j = i + 1; j <= n; j++) {
      cout << i << " " << j << " ---> " << getlca(i, j) << "\n";
      assert(getlca(i, j) == getlca(j, i));
    }
  }*/
  /*for (int i = 1; i <= n; i++) {
    for (auto &it : g[i]) {
      int j = it.first, c = it.second;
      if (i < j) {
        cout << i << " " << j << " " << c << "\n";
      }
    }
  }*/
}

int valueOf[N], par[N], root;
vector<pair<int, ll>> secondg[N];

const ll INF = (ll) 1e18 + 7;

ll best;
ll mn1[N];
ll mn2[N];

void dfs(int a) {

  mn1[a] = mn2[a] = INF;
  if (valueOf[a] == 1) {
    mn1[a] = 0;
  }
  if (valueOf[a] == 2) {
    mn2[a] = 0;
  }
  for (auto &it : secondg[a]) {
    int b = it.first;
    ll c = it.second;
    assert(dep[b] > dep[a]);
    dfs(b);
    mn1[a] = min(mn1[a], mn1[b] + c);
    mn2[a] = min(mn2[a], mn2[b] + c);
  }
  best = min(best, mn1[a] + mn2[a]);
}

long long Query(int s, int x[], int t, int y[]) {
  vector<pair<int, int>> guys;
  for (int i = 0; i < s; i++) {
    guys.push_back({indexOfNode[x[i] + 1], x[i] + 1});
    valueOf[x[i] + 1] = 1;
  }
  for (int i = 0; i < t; i++) {
    guys.push_back({indexOfNode[y[i] + 1], y[i] + 1});
    valueOf[y[i] + 1] = 2;
  }

  sort(guys.begin(), guys.end());

  vector<pair<int, int>> secondGuys = guys;
  for (int i = 1; i < (int) guys.size(); i++) {
    int node = getlca(guys[i - 1].second, guys[i].second);
    secondGuys.push_back({indexOfNode[node], node});
  }
  sort(secondGuys.begin(), secondGuys.end());

  assert(!secondGuys.empty());

  vector<int> path;

  root = secondGuys[0].second;
  par[root] = 0;
  path.push_back(root);


  for (int it = 1; it < (int) secondGuys.size(); it++) {
    if (secondGuys[it] == secondGuys[it - 1]) {
      continue;
    }
    int node = secondGuys[it].second;
    while (1) {
      assert(!path.empty());
      int lca = getlca(node, path.back());
      if (lca != path.back()) {
        path.pop_back();
      } else {
        break;
      }
    }
    par[node] = path.back();
    path.push_back(node);
  }


  for (int ite = 1; ite < (int) secondGuys.size(); ite++) {
    if (secondGuys[ite] == secondGuys[ite - 1]) {
      continue;
    }
    auto &it = secondGuys[ite];
    int x1 = par[it.second];
    int x2 = it.second;
    assert(dep[x1] < dep[x2]);
    secondg[par[it.second]].push_back({it.second, sum[it.second] - sum[par[it.second]]});
  }

  for (int i = 1; i <= n; i++) {
    for (auto &it : secondg[i]) {
      assert(dep[i] < dep[it.first]);
    }
  }

  best = INF;
  dfs(root);
  for (auto &it : secondGuys) {
    valueOf[it.second] = 0;
    par[it.second] = 0;
    secondg[it.second].clear();
  }
  return best;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24376 KB Output is correct
2 Correct 811 ms 33644 KB Output is correct
3 Correct 812 ms 33604 KB Output is correct
4 Correct 842 ms 33844 KB Output is correct
5 Correct 725 ms 34132 KB Output is correct
6 Correct 513 ms 33692 KB Output is correct
7 Correct 801 ms 33752 KB Output is correct
8 Correct 820 ms 34184 KB Output is correct
9 Correct 699 ms 34040 KB Output is correct
10 Correct 480 ms 33604 KB Output is correct
11 Correct 811 ms 33636 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24140 KB Output is correct
2 Execution timed out 8084 ms 229476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24376 KB Output is correct
2 Correct 811 ms 33644 KB Output is correct
3 Correct 812 ms 33604 KB Output is correct
4 Correct 842 ms 33844 KB Output is correct
5 Correct 725 ms 34132 KB Output is correct
6 Correct 513 ms 33692 KB Output is correct
7 Correct 801 ms 33752 KB Output is correct
8 Correct 820 ms 34184 KB Output is correct
9 Correct 699 ms 34040 KB Output is correct
10 Correct 480 ms 33604 KB Output is correct
11 Correct 811 ms 33636 KB Output is correct
12 Correct 16 ms 24140 KB Output is correct
13 Execution timed out 8084 ms 229476 KB Time limit exceeded
14 Halted 0 ms 0 KB -