oj.uz

Submission #499061

# Submission time Handle Problem Language Result Execution time Memory
499061 2021-12-27T07:21:08 Z 600Mihnea Factories (JOI14_factories) C++17
100 / 100
 2512 ms 280712 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];
  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))]);
    }
  }
}

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;
    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());


  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) {
      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;
    secondg[par[it.second]].push_back({it.second, sum[it.second] - sum[par[it.second]]});
  }

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

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:150:9: warning: unused variable 'x1' [-Wunused-variable]
  150 |     int x1 = par[it.second];
      |         ^~
factories.cpp:151:9: warning: unused variable 'x2' [-Wunused-variable]
  151 |     int x2 = it.second;
      |         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24288 KB Output is correct
2 Correct 762 ms 33616 KB Output is correct
3 Correct 766 ms 33684 KB Output is correct
4 Correct 790 ms 33796 KB Output is correct
5 Correct 646 ms 33944 KB Output is correct
6 Correct 494 ms 33672 KB Output is correct
7 Correct 746 ms 33672 KB Output is correct
8 Correct 807 ms 33988 KB Output is correct
9 Correct 636 ms 34088 KB Output is correct
10 Correct 476 ms 33628 KB Output is correct
11 Correct 767 ms 33756 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24140 KB Output is correct
2 Correct 1411 ms 231256 KB Output is correct
3 Correct 1469 ms 235572 KB Output is correct
4 Correct 1092 ms 231864 KB Output is correct
5 Correct 1348 ms 274848 KB Output is correct
6 Correct 1688 ms 255512 KB Output is correct
7 Correct 1321 ms 84916 KB Output is correct
8 Correct 860 ms 84876 KB Output is correct
9 Correct 1071 ms 91812 KB Output is correct
10 Correct 1252 ms 86476 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24288 KB Output is correct
2 Correct 762 ms 33616 KB Output is correct
3 Correct 766 ms 33684 KB Output is correct
4 Correct 790 ms 33796 KB Output is correct
5 Correct 646 ms 33944 KB Output is correct
6 Correct 494 ms 33672 KB Output is correct
7 Correct 746 ms 33672 KB Output is correct
8 Correct 807 ms 33988 KB Output is correct
9 Correct 636 ms 34088 KB Output is correct
10 Correct 476 ms 33628 KB Output is correct
11 Correct 767 ms 33756 KB Output is correct
12 Correct 15 ms 24140 KB Output is correct
13 Correct 1411 ms 231256 KB Output is correct
14 Correct 1469 ms 235572 KB Output is correct
15 Correct 1092 ms 231864 KB Output is correct
16 Correct 1348 ms 274848 KB Output is correct
17 Correct 1688 ms 255512 KB Output is correct
18 Correct 1321 ms 84916 KB Output is correct
19 Correct 860 ms 84876 KB Output is correct
20 Correct 1071 ms 91812 KB Output is correct
21 Correct 1252 ms 86476 KB Output is correct
22 Correct 2340 ms 249940 KB Output is correct
23 Correct 2177 ms 250240 KB Output is correct
24 Correct 2512 ms 255136 KB Output is correct
25 Correct 2458 ms 254736 KB Output is correct
26 Correct 2330 ms 245052 KB Output is correct
27 Correct 2264 ms 280712 KB Output is correct
28 Correct 1440 ms 246764 KB Output is correct
29 Correct 2319 ms 242628 KB Output is correct
30 Correct 2274 ms 243052 KB Output is correct
31 Correct 2276 ms 242036 KB Output is correct
32 Correct 1080 ms 95104 KB Output is correct
33 Correct 838 ms 88792 KB Output is correct
34 Correct 1372 ms 83732 KB Output is correct
35 Correct 1369 ms 83492 KB Output is correct
36 Correct 1476 ms 84416 KB Output is correct
37 Correct 1376 ms 84348 KB Output is correct